Minimum Number of Refueling Stops Hard 0 attempts
LeetCode ↗

Minimum Number of Refueling Stops

Hard HeapPriority Queue LeetCode

A car begins a trip with startFuel units of fuel in its tank and must travel a distance of target. Along the route sit several gas stations, each given as a [position, fuel] pair describing its location and how much fuel it adds to the tank. One unit of fuel covers one unit of distance. Work out the fewest refueling stops needed to reach (or pass) target, or return -1 if the car can't make it.

Input Format
Implement minRefuelStops(target, startFuel, stations). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 3

Input
target = 100
startFuel = 1
stations = [[10,100]]
Output
-1
Constraints
  • 1 <= target <= 10^9
  • 0 <= startFuel <= 10^9
  • 0 <= stations.length <= 500
  • Stations are sorted by increasing position; positions and fuel amounts are positive integers.
Test Cases (3)
Case 1
Args: [100,10,[[10,60],[20,30],[30,30],[60,40]]] Expected: 2
Case 2
Args: [1,1,[]] Expected: 0
Case 3
Args: [100,1,[[10,100]]] Expected: -1
Topics
HeapPriority Queue

Greedy with Max-Heap

As you pass stations, add their fuel to a max-heap. When empty, refuel from the largest available.

javascript
function minRefuelStops(target, startFuel, stations) {

  const heap = [];
  function push(value) {
    heap.push(value); let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i-1)/2); if (heap[p] >= heap[i]) break;
      [heap[p],heap[i]] = [heap[i],heap[p]]; i = p;
    }
  }
  function pop() {
    const max = heap[0], last = heap.pop();
    if (heap.length) {
      heap[0] = last; let i = 0;
      while (2*i+1 < heap.length) {
        let child = 2*i+1;
        if (child+1 < heap.length && heap[child+1] > heap[child]) child++;
        if (heap[i] >= heap[child]) break;
        [heap[i],heap[child]] = [heap[child],heap[i]]; i = child;
      }
    }
    return max;
  }
  let fuel = startFuel, stops = 0, i = 0;
  while (fuel < target) {
    while (i < stations.length && stations[i][0] <= fuel) push(stations[i++][1]);
    if (!heap.length) return -1;
    fuel += pop(); stops++;
  }
  return stops;
}

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

Saved in this browser only. Private to you.

JavaScript