Question

Gas stations optimization. There are n gas station S1, …, Sn along I-80 from San Francisco to New York. On a full tank of gas your car goes for D miles. Gas station S1 is in San Francisco, each gas station Si, for 2 ≤ i ≤ n, is di ≤ D miles after the previous gas station Si-1, and gas Sn is in New York. What is the minimum number of gas stops you must make when driving from San Francisco to New York? Give the pseudo-code for a greedy algorithm that solves the above optimization problem. Justify briefly why your algorithm finds the optimum solution. What is the asymptotic running time of your algorithm in term of n?

Answer 1

There are n gas stations S₁,S₂,... , S_n.

Total distance to be travelled is 80.

On full tank, the car goes for D miles.

For the greedy algorithm, we go as far as we can before refuelling the vehicle.

The pseudo-code for the given algorithm is as follows:

countOfStops = 0

x = 0 //current distance

while(x!=S_n)

let p be the largest integer where S_p <= x+D

x=Sp

countOfStops++;  

return countOfStops;

Since at any steps we go as far as we can before refuelling, it gives us the optimal solution.

Here we scan the entire S array once. So the complexity is O(n).