Minimum Number of Refueling Stops
A car drives from position 0 to position target. It starts with startFuel litres, and one litre moves it one unit of distance. Along the way there are fuel stations, given as [position, fuel]. Stopping at a station adds all of its fuel to the tank, which has no size limit. Stations may be used in any order you can reach them in. Return the smallest number of stops needed to reach target, or -1 when the trip is impossible. Drive as far as the fuel allows, and as you pass each station remember its fuel without spending a stop . When the car cannot reach target yet, it must have stopped somewhere behind it, and the best choice is always the biggest tank you drove past. A max-heap of the passed fuel amounts gives you that instantly, and taking them biggest first keeps the number of stops as low as possible.
Constraints
- 1 ≤ target ≤ 109
- 0 ≤ startFuel ≤ 109
- 0 ≤ stations.length ≤ 500
- Stations are given in increasing order of position, and every position is before target
Example
target = 100, startFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]]2Explanation Drive 10 units to the first station and take its 60 litres, giving a range of 70. That reaches past the stations at 20, 30 and 60. Take the 40 litre station, giving a range of 110, which is past the target. Two stops are enough.
In plain terms
- Heap
- A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
- Backing array
- A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
- Max-heap
- A heap whose best item is the largest one. Popping it always hands you the biggest fuel amount you have driven past and not yet used.
- Deciding in hindsight
- The car never has to guess whether to stop at a station. It drives past, keeps the option in the heap, and only cashes in an option when it actually runs short.
- Impossible trip
- If the car is short of fuel and the heap is empty, there is no station behind it left to use, so the answer is -1.
The row of boxes is the backing array of the max-heap holding the fuel of every station driven past but not yet used
The car starts with 10 litres, so it can reach position 10. Nothing is in the heap yet.
What happens in this step
target = 100, fuel = 10, stops = 0 stations = [10, 60], [20, 30], [30, 30], [60, 40] heap is empty fuel = 10 is less than target = 100, so the car will need to stop.
Steps to visualize
- Each box is one slot of the list that stores the heap. Slot 0 always holds the biggest unused fuel amount.
- A slot showing — is unused right now.
- The variable fuel means how far from position 0 the car can currently reach.
- First, add every station at or before that reach into the heap. Those are free to consider, and cost no stop.
- Then, if the car still cannot reach target, pop the biggest amount, count one stop, and repeat.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
The car starts with 10 litres, so it can reach position 10. Nothing is in the heap yet.
What happens in this step
target = 100, fuel = 10, stops = 0 stations = [10, 60], [20, 30], [30, 30], [60, 40] heap is empty fuel = 10 is less than target = 100, so the car will need to stop.
Solution
function minRefuelStops(target, startFuel, stations) {
const reachable = new Heap((a, b) => b - a);
let fuel = startFuel;
let stops = 0;
let next = 0;
while (fuel < target) {
while (next < stations.length && stations[next][0] <= fuel) {
reachable.push(stations[next][1]);
next++;
}
if (reachable.size() === 0) return -1;
fuel += reachable.pop();
stops++;
}
return stops;
}
class Heap {
constructor(compare) {
this.items = [];
this.compare = compare;
}
size() {
return this.items.length;
}
peek() {
return this.items[0];
}
push(value) {
this.items.push(value);
let child = this.items.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (this.compare(this.items[child], this.items[parent]) >= 0) break;
const swap = this.items[child];
this.items[child] = this.items[parent];
this.items[parent] = swap;
child = parent;
}
}
pop() {
const top = this.items[0];
const last = this.items.pop();
if (this.items.length > 0) {
this.items[0] = last;
let parent = 0;
while (true) {
const left = parent * 2 + 1;
const right = parent * 2 + 2;
let best = parent;
if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
if (best === parent) break;
const swap = this.items[parent];
this.items[parent] = this.items[best];
this.items[best] = swap;
parent = best;
}
}
return top;
}
}- Time
- O(n log n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
target = 100, startFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]] | 2 | example from the docstring |
target = 1, startFuel = 1, stations = [] | 0 | smallest input, the car already has enough fuel |
target = 100, startFuel = 1, stations = [[10, 100]] | -1 | the only station is out of reach, so the trip is impossible |
target = 100, startFuel = 50, stations = [[25, 25], [50, 25], [75, 25]] | 2 | equal fuel amounts, so the order of popping does not matter |
target = 100, startFuel = 100, stations = [[50, 50]] | 0 | a station is driven past and never needed |
target = 1000, startFuel = 299, stations = ten stations between 13 and 841 | 4 | larger input where only the biggest four tanks are used |