Minimum Number of Refueling Stops

A car travels from a starting position to a destination that is target miles east of the start. There are gas stations along the way, given as an array stations, where stations[i] = [positioni, fueli] means the ith gas station is positioni miles east of the start, and has fueli liters of gas available.

Minimum Number of Refueling Stops

Problem Statement

A car travels from a starting position to a destination that is target miles east of the start.

There are gas stations along the way, given as an array stations, where stations[i] = [positioni, fueli] means the ith gas station is positioni miles east of the start, and has fueli liters of gas available.

The car has an infinite tank, starting with startFuel liters of fuel. It uses one liter of gas per mile driven. When the car reaches a gas station, it can stop and refuel, transferring all the gas from that station into the car.

Return the minimum number of refueling stops needed to reach the destination. If it's not possible to reach the destination, return -1.

Note: If the car reaches a gas station with 0 fuel left, it can still refuel there. If the car reaches the destination with exactly 0 fuel left, it still counts as having arrived successfully.

Examples

Example 1

Input: target = 1, startFuel = 1, stations = []

Output: 0

Explanation: We can reach the target without needing to refuel at all.

Example 2

Input: target = 100, startFuel = 1, stations = [[10,100]]

Output: -1

Explanation: We can't reach the target, or even the first gas station.

Example 3

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

Output: 2

Explanation:

We start with 10 liters of fuel.

We drive to position 10, using up all 10 liters. We refuel there, going from 0 liters to 60 liters.

Then we drive from position 10 to position 60 (using 50 liters), and refuel again, going from 10 liters to 50 liters. We then drive the rest of the way and reach the target.

We made 2 refueling stops, so we return 2.

Constraints

• 1 ≤ target, startFuel ≤ 10⁹
• 0 ≤ stations.length ≤ 500
• 1 ≤ positioni < positioni+1 < target
• 1 ≤ fueli < 10⁹

Solution

The main idea is to drive as far as we can, and along the way, keep track of every gas station we've passed, storing their fuel amounts in a max heap. Whenever we're about to run out of fuel, we grab the largest fuel amount we've collected so far and use it, since that gets us the farthest.

Steps

• If startFuel is already enough to reach target directly, we return 0 — no stops needed.
• We track maxDistance, which represents the farthest point we can currently reach with our fuel.
• We go through the stations in order, using a pointer i:
  • If the next station is within reach (its position is less than or equal to maxDistance), we haven't "used" this station's fuel yet — we just add its fuel amount into our max heap, in case we need it later.
  • If the next station is too far to reach right now, that means we need to refuel using fuel we've already collected:
    • If our max heap is empty, we have no more fuel options left, and we still can't reach the next station. This means the trip is impossible, so we return -1.
    • Otherwise, we take the largest fuel amount from the heap, add it to maxDistance, and count this as one more stop.
• We repeat this until maxDistance reaches or passes target. At that point, we return the total number of stops made.

Code

function minRefuelStops(target, startFuel, stations) {
    if (startFuel >= target) {
        return 0;
    }

    let maxHeap = new MaxHeap();

    let i = 0;
    let n = stations.length;
    let stops = 0;
    let maxDistance = startFuel;

    while (maxDistance < target) {
        if (i < n && stations[i][0] <= maxDistance) {
            maxHeap.push(stations[i][1]);
            i++;
        } else if (maxHeap.isEmpty()) {
            return -1;
        } else {
            maxDistance += maxHeap.pop();
            stops++;
        }
    }

    return stops;
}