DSA problem
Minimum Number of Refueling Stops
A car travels from a starting position to a destination which is target miles east of the starting position. There are gas stations along the way, represented as an array stations where stations[i] = [position_i, fuel_i] indicates the i-th gas station is position_i miles east of the starting position and has fuel_i liters of gas. The car starts with an infinite tank but begins with startFuel liters of fuel. It uses one liter of fuel per mile. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car. Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1. Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
The naive approach is dynamic programming: dp[i] is the farthest distance reachable with i refuels. That gives an O(n^2) algorithm — useful but not as elegant as the greedy.
The greedy formulation imagines you have already passed several stations but skipped them; their fuel is "saved up" and available for later use. A max-heap stores the fuel of every station passed-but-not-yet-used. Walk the stations in order of position. Before reaching station i (or the destination), if the current fuel is not enough, pop the largest fuel from the heap and "retroactively" use it, incrementing the refuel count. Repeat until fuel suffices or the heap is empty (then return -1).
This deferred-decision greedy is provably optimal: any optimal sequence of refuels can be transformed by swapping a smaller skipped station for a larger skipped one without increasing the refuel count. The algorithm runs in O(n log n) time with O(n) heap space, where n is the number of stations.
Examples
target = 1, startFuel = 1, stations = []0target = 100, startFuel = 1, stations = [[10,100]]-1target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]2Constraints
- 1 <= target, startFuel <= 10^9
- 0 <= stations.length <= 500
- 1 <= position_i < position_{i+1} < target
- 1 <= fuel_i <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.