Minimum Number of Refueling Stops [Hard] — Greedy Max-Heap

Problem Statement

A car starts at position 0 with startFuel. At each station [position, fuel] you can refuel. Return min stops to reach target, or -1 if impossible.

Input: target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]]
Output: 2

Intuition

Use a max-heap of fuel amounts passed. Sweep stations. If we can't reach the next stop, greedily refuel from the largest fuel station we've passed.

Solutions

C++

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

Java

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
    int fuel=startFuel, stops=0, i=0;
    pq.offer(0);
    // add target as final station
    int n=stations.length;
    for(int pos=0;;){
        while(i<n&&stations[i][0]<=fuel){pq.offer(stations[i][1]);i++;}
        if(fuel>=target) return stops;
        if(pq.isEmpty()) return -1;
        fuel+=pq.poll(); stops++;
    }
}

Python

import heapq

def minRefuelStops(target: int, startFuel: int, stations: list[list[int]]) -> int:
    heap = []  # max-heap (negate values)
    stations.append([target, 0])
    fuel, stops = startFuel, 0
    for pos, cap in stations:
        while fuel < pos:
            if not heap:
                return -1
            fuel -= heapq.heappop(heap)  # add largest
            stops += 1
        heapq.heappush(heap, -cap)
    return stops

Complexity

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