Jack plans to drive from city A to city B along a highway. Suppose g0, g1, g2, …, gk are the gas stations along the highway and are ordered in increasing distance (in miles) from city A, where g0 is located at the starting place (city A). Let di be the distance (in miles) between gi and gi+1 , i = 0, …, k – 1, and we assume that these distances are known to Jack. Each time Jack fills gas to his car, he gets a full tank of gas. Jack also knows the number of miles, m, his car can drive with a full tank of gas. Jack’s goal is to minimize the number of times he needs to stop at gas stations for his trip.
a. Design a greedy algorithm to solve the above problem, i.e., to minimize the number of stops for gas.
b. Show that your greedy algorithm has the greedy choice property, i.e., each local decision will lead to the optimal solution. Basically you need to argue for the correctness of your algorithm.
c. What is the running time of your algorithm?
