Minimum Number of Refueling Stops
Problem
A car starts with startFuel units of fuel and must reach a target miles away; one mile costs one unit. Along the way there are gas stations, where stations[i] = [position, fuel]. Return the minimum number of refueling stops to reach the target, or -1 if impossible.
target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]2import heapq
def min_refuel_stops(target, start_fuel, stations):
heap, fuel, i, stops = [], start_fuel, 0, 0
while fuel < target:
while i < len(stations) and stations[i][0] <= fuel:
heapq.heappush(heap, -stations[i][1])
i += 1
if not heap:
return -1
fuel += -heapq.heappop(heap)
stops += 1
return stopsfunction minRefuelStops(target, startFuel, stations) {
const heap = new MaxHeap(); // largest fuel on top
let fuel = startFuel, i = 0, stops = 0;
while (fuel < target) {
while (i < stations.length && stations[i][0] <= fuel)
heap.push(stations[i++][1]);
if (heap.isEmpty()) return -1;
fuel += heap.pop();
stops++;
}
return stops;
}int minRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
long fuel = startFuel;
int i = 0, stops = 0;
while (fuel < target) {
while (i < stations.length && stations[i][0] <= fuel)
heap.add(stations[i++][1]);
if (heap.isEmpty()) return -1;
fuel += heap.poll();
stops++;
}
return stops;
}int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
priority_queue<int> heap;
long long fuel = startFuel;
int i = 0, stops = 0;
while (fuel < target) {
while (i < (int)stations.size() && stations[i][0] <= fuel)
heap.push(stations[i++][1]);
if (heap.empty()) return -1;
fuel += heap.top(); heap.pop();
stops++;
}
return stops;
}Explanation
We want to reach the target with the fewest refuels. The clever idea is that we don't have to decide to refuel at a station when we pass it — we can pretend each passed station's fuel is "banked" and grab it later, only when we actually run out.
We keep a max-heap of banked fuel amounts. As our reachable distance (fuel) grows, every station whose position is within reach gets pushed into the heap. We don't spend it yet — we just remember it's available.
When fuel < target and we can't go further with what we have, we refuel greedily with the largest banked tank by popping the heap top, adding it to fuel, and counting one stop. Taking the biggest available fuel each time minimizes the number of stops.
If we ever need to refuel but the heap is empty, no reachable station can help, so we return -1.
Example: target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]]. With 10 fuel we reach the station at 10 and bank 60. We run dry, so we take the biggest banked tank (60), reaching mile 70; that unlocks the 40-fuel station, which we take next to pass 100. That's 2 stops.