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, k)
Input: Array A[0..n] where A[i] is distance of i-th watering stop, D is distance of race, k is the number of miles runner can run on a bottle of water
Output: Sequence S of watering stops for the runner minimizing number of stops
