Problem 4. (10 points) A long distance runner wants to carry only a single water bottle along the route and she can run k miles on one bottle of water. Before the race, she is given a map of all n watering stops (i.e. mile markers of these stops). Assume that the distance between successive watering stops is no more than k miles. Design an efficient greedy algorithm (by completing the algorithm below) for determining where she should take a new bottle in order to make as few stops as possible. Derive its asymptotic time complexity. MinStops(A, D) Input: Array A[0..n) where A[i] is distance of i-th watering stop, D is distance of race Output: Sequence S of watering stops for the runner minimizing number of stops