Minimum Number of Refueling Stops

Car starts with startFuel, reach target using stations. Minimize number of refueling stops.

Example 1

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

Example 2

Input: target=1, startFuel=1, stations=[] → Output: 0

Solution Approach

Greedy with max-heap: drive as far as possible. When out of fuel, greedily refuel at station with most fuel seen so far.

Add all passed stations to max-heap by fuel
When current fuel < next required distance
Poll max from heap and add to fuel (stops++)
If heap empty but still cant reach, return -1
Return stops count

Java

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> pq = 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 && !pq.isEmpty()) {
            fuel += pq.poll();
            stops++;
        }
        if (fuel < 0) return -1;
        pq.offer(s[1]);
    }
    fuel -= target - prev;
    while (fuel < 0 && !pq.isEmpty()) {
        fuel += pq.poll();
        stops++;
    }
    return fuel >= 0 ? stops : -1;
}

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