Suppose that you will drive your car for a long trip between Worcester, Massachusetts and San Francisco, California along Interstate Highways. In preparation for your trip, you have downloaded a map that contains the distances in miles between all the gas stations in your route. Assume that your car's gas tank, when full, holds enough gas to travel n miles. Assume that the value n is given. The distance between Worcester and San Francisco is irrelevant for this problem.

Assume that you want to make the minimum number of stops possible along the way, without running out of gas at any point. Describe in detail an efficient method by which you can determine at which gas stations you should stop.

Solution:
The following greedy approach works: Start your trip in Worcester with a full tank. Check your map to determine the farthest away gas station in your route within n miles. Stop at that gas station, fill up your tank and check your map again to determine the farthest away gas station in your route within n miles from this stop. Repeat the process until you get to San Francisco.