Minimum Number of Refueling Stops

Problem

A car starts with startFuel. Gas stations along the route have (position, fuel). Return minimum stops to reach target, or -1.

Key insight (Greedy): Drive as far as possible. When out of fuel, retroactively "stop" at the station with the most fuel seen so far (max-heap). This minimizes stops.

Solutions

// C++
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    priority_queue<int> maxH;
    int fuel = startFuel, stops = 0, prev = 0;
    stations.push_back({target, 0});
    for (auto& s : stations) {
        fuel -= (s[0] - prev);
        prev = s[0];
        while (fuel < 0 && !maxH.empty()) { fuel += maxH.top(); maxH.pop(); stops++; }
        if (fuel < 0) return -1;
        maxH.push(s[1]);
    }
    return stops;
}

// Java
public int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
    int fuel = startFuel, stops = 0, prev = 0;
    for (int[] s : stations) {
        fuel -= s[0] - prev; prev = s[0];
        while (fuel < 0 && !maxH.isEmpty()) { fuel += maxH.poll(); stops++; }
        if (fuel < 0) return -1;
        maxH.offer(s[1]);
    }
    fuel -= target - prev;
    while (fuel < 0 && !maxH.isEmpty()) { fuel += maxH.poll(); stops++; }
    return fuel < 0 ? -1 : stops;
}

# Python
import heapq

def minRefuelStops(target, startFuel, stations):
    heap = []  # max-heap (negate fuel)
    fuel = startFuel
    stops = 0
    prev = 0
    stations.append((target, 0))
    for pos, f in stations:
        fuel -= pos - prev
        prev = pos
        while fuel < 0 and heap:
            fuel -= heapq.heappop(heap)  # adds back (negated)
            stops += 1
        if fuel < 0:
            return -1
        heapq.heappush(heap, -f)
    return stops

// JavaScript
function minRefuelStops(target, startFuel, stations) {
    stations.push([target, 0]);
    const heap = []; // sorted descending
    let fuel = startFuel, stops = 0, prev = 0;
    for (const [pos, f] of stations) {
        fuel -= pos - prev; prev = pos;
        while (fuel < 0 && heap.length) { fuel += heap.shift(); stops++; }
        if (fuel < 0) return -1;
        let ins = heap.findIndex(x => x < f);
        if (ins === -1) heap.push(f); else heap.splice(ins, 0, f);
    }
    return stops;
}

Complexity

Time: O(n log n)
Space: O(n)

Key Insight

Greedy with hindsight: collect all stations as we pass them. Only "stop" when we run out — always choosing the richest past station minimizes total stops.