Minimum Fuel Stops to Destination
Problem Description
You are driving along a straight highway of total length `roadLength` miles. Your car starts with `startFuel` units of fuel. Along the road there are `n` fuel stations, each described by `[position, fuelAmount]`, where `position` is the distance from the start and `fuelAmount` is how much fuel you can pick up there.
Your car consumes exactly 1 unit of fuel per mile. You want to reach the destination (at mile `roadLength`) stopping at the **fewest** number of stations possible.
Return the minimum number of fuel stops needed to reach the destination, or `-1` if it is impossible.
**Example 1:**
```
Input: roadLength = 100, startFuel = 10, stations = [[10,60],[20,30],[30,40],[60,40]]
Output: 2
Explanation: Stop at station 0 (pick up 60), then stop at station 3 (pick up 40). Total stops = 2.
```
**Example 2:**
```
Input: roadLength = 50, startFuel = 5, stations = [[25,10]]
Output: -1
Explanation: Cannot reach mile 25 with only 5 units of fuel.
```
Constraints
- 1 <= roadLength <= 10^9
- 0 <= startFuel <= roadLength
- 0 <= stations.length <= 500
- 0 < stations[i][0] < roadLength
- 1 <= stations[i][1] <= 10^9
- Stations are given in strictly increasing order of position.
Follow-up
What if each station has a limit on how many times you can refuel (e.g. at most once per visit)? Extend the solution to handle a cost per stop that varies by station.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.