You plan to drive from city A to city B along a highway and

You plan to drive from city A to city B along a highway and you have a map showing distances between gas stations on your route. Your car’s gas tank, when full, holds enough gas to travel k kilometers. You wish to make as few gas stops as possible along the way. Give an efficient algorithm to determine at which gas stations to stop and prove that your algorithm gives you an optimal solution.

Solution

Answer:

The algorithm is :

1. Start the journey in A with a full tank.

2. Check your map to determine the farthest gas station with n miles.

3. Stop and fill the tank and check again n miles from this stop.

4. REPEAT the same untill you reach to B.

See here the greedy method selected as the first stop the gas station farthest away from B n miles from A. But no optimal method could have selected a farther way from gas station . Hence the greedy method is doing worse than the optimal here.