Fewest Refuels on the Highway
HardGreedy
Problem
A car drives east from mile 0 to mile target, using one litre per mile, and starts with startFuel litres. The tank has no capacity limit. stations[i] = [position, fuel] lists the fuel stations in increasing order of position; stopping at a station adds all of its fuel.
Return the minimum number of stops needed to reach target, or -1 if it is impossible. Arriving anywhere with exactly 0 litres still counts as arriving.
Example 1
- Input:
- target = 120, startFuel = 20, stations = [[10, 40], [20, 10], [50, 70], [90, 15]]
- Output:
- 2
Stop at mile 10 (fuel lasts to mile 60), then at mile 50 (lasts to mile 130).
Example 2
- Input:
- target = 100, startFuel = 1, stations = [[10, 100]]
- Output:
- -1
The car runs dry at mile 1.
Constraints
- 1 ≤ target, startFuel ≤ 10^9
- 0 ≤ stations.length ≤ 500
- 0 < position < target, positions strictly increasing
- 1 ≤ fuel ≤ 10^9
Hint
Show the first hint
You do not need to decide at a station whether to stop. What if you could decide later?
Walkthrough
How to approach it
01Clarify before coding
- Is the tank unlimited? Yes, so stopping never wastes fuel.
- Does reaching a station with 0 fuel count? Yes.
- Are stations sorted by position? Yes, strictly increasing.
02Brute force
DP: farthest[k] = the farthest mile reachable using exactly k stops, updated station by station (like a knapsack in reverse order of k).
Cost: O(n²) with n ≤ 500 is actually fine, but the greedy heap solution is O(n log n) and is what the 'Hard' label is testing.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.