Description
A car travels from start to target miles away, starting with startFuel. Given gas stations, return the minimum number of refueling stops to reach the target, or -1 if impossible.
Examples
Input:
target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]Output:
2Explanation:
Refuel at stations 0 and 3.
Input:
target = 200, startFuel = 50, stations = [[25,25],[50,50],[100,100],[150,75]]Output:
2Explanation:
Start with 50 fuel, can reach position 50. Refuel at station 1 (position 50, +50 fuel) giving 100 total fuel. Can now reach position 100. Refuel at station 2 (position 100, +100 fuel) giving 200 total fuel. Can now reach target at position 200. Need exactly 2 refueling stops.
Input:
target = 80, startFuel = 80, stations = [[20,15],[40,20],[60,30]]Output:
0Explanation:
The car starts with 80 fuel and the target is 80 miles away. Since startFuel equals the target distance, the car can reach the destination without any refueling stops.
Constraints
- •
1 ≤ target, startFuel ≤ 10⁹ - •
0 ≤ stations.length ≤ 500