534. Minimum Number of Refueling Stops
A car leaves position 0 and drives east toward a destination target miles away, burning exactly one liter of fuel per mile. It starts with start_fuel liters in an infinitely large tank.
Along the road sit gas stations, given as stations[i] = [position_i, fuel_i]: the i-th station is position_i miles from the start and holds fuel_i liters. Positions are strictly increasing and all lie before the target. When the car is at a station it may stop and pump the station's entire supply into the tank.
Return the fewest refueling stops needed to reach the destination, or -1 if it is impossible. Arriving anywhere — a station or the target — with exactly 0 liters left still counts as arriving.
Example 1:
Input: target = 100, startFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]]
Output: 2
Explanation: Drive 10 miles to the first station and take its 60 liters (stop 1) — total range is now 70 miles. Roll on to the station at mile 60 and take its 40 liters (stop 2), enough to coast into mile 100. No single stop gets there.
Example 2:
Input: target = 100, startFuel = 1, stations = [[10, 100]]
Output: -1
Explanation: One liter moves the car exactly one mile, so it dies at mile 1 and never even reaches the station at mile 10.
Constraints:
- 1 ≤ target, startFuel ≤ 10⁹
- 0 ≤ stations.length ≤ 500
- 1 ≤ position_i < position_{i+1} < target
- 1 ≤ fuel_i ≤ 10⁹
Hints:
Greedy rules like "refuel at the nearest station when running low" fail — the choice of *which* stations to use matters far more than when you commit to them.
Refuel retroactively: drive as far as the current fuel allows, and only when you fall short, grab the largest fuel load among stations you have already driven past. A max-heap of passed-by fuel amounts makes each grab O(log n).
There is also a knapsack-style DP: let dp[t] be the farthest mile reachable using exactly t stops, and fold in the stations one at a time, iterating t downward so each station is used at most once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: target = 100, startFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]]
Expected output: 2