You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel.
At most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at
Distances stop1, stop2, . . . , stop𝑛 from your home city. What is the minimum number of refills needed?
Input Format. The first line contains an integer 𝑑. The second line contains an integer 𝑚. The third line
Specifies an integer 𝑛. Finally, the last line contains integers stop1, stop2, . . . , stop𝑛.
Assuming that the distance between the cities is 𝑑 miles, a car can travel at most 𝑚 miles
On a full tank, and there are gas stations at distances stop1, stop2, . . . , stop𝑛 along the way, output the
Minimum number of refills needed. Assume that the car starts with a full tank. If it is not possible to
Reach the destination, output −1.
1 ≤ 𝑑 ≤ 105. 1 ≤ 𝑚 ≤ 400. 1 ≤ 𝑛 ≤ 300. 0 < stop1 < stop2 < · · · < stop𝑛 < 𝑑.
950 400 4 200 375 550 750
The distance between the cities is 950, the car can travel at most 400 miles on a full tank. It suffices
to make two refills: at points 375 and 750. This is the minimum number of refills as with a single refill
One would only be able to travel at most 800 miles.
10 3 4 1 2 5 9
One cannot reach the gas station at point 9 as the previous gas station is too far away.
Make a greedy choice!
Reduce to a smaller problem
A greedy choice is a safe move if there is an optimal solution consistent with the first move:
Refill at the closest gas station
Refill at the farthest reachable gas station
Go until the fuel finishes up!
Here, n is the total number of stops, x is an array with distance d i.e. x [d], currentRefill, lastRefills are nothing but indexes. Also, numRefills is the minimum number of fills.
This problem is been practiced on Coursera platform under the the course ‘Algorithms Toolbox’.