Problem Introduction
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?
Problem Description
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๐.
Output Format
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.
Constraints
1 โค ๐ โค 105. 1 โค ๐ โค 400. 1 โค ๐ โค 300. 0 < stop1 < stop2 < ยท ยท ยท < stop๐ < ๐.
Sample 1
Input:
950
400
4
200 375 550 750
Output:
2
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.
Sample 2
Input:
10
3
4
1 2 5 9
Output:
1
One cannot reach the gas station at point 9 as the previous gas station is too far away.
Greedy Strategy

Make a greedy choice!

Reduce to a smaller problem

Iterate
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!
Implementation
the algorithm
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.
Code
This problem is been practiced on Coursera platform under the the course โAlgorithms Toolboxโ.