DSA Factory
Free Greedy lessonsGreedy · Stage 4 · Mastery · Step 3

Fewest fuel stops

Drive to a target with the fewest stops to refuel, by remembering the stations you passed and fuelling retroactively at the biggest one only when you would otherwise run out. About 25 minutes.

Decide as late as possible

A car starts with some fuel and uses one unit per distance unit. Stations along the way hold fuel you may take in full, and each one you use is a stop. Reach the target with the fewest stops.

Do not decide at each station. Drive past it, but write down how much it offered. Only when you would run out do you look back and pretend you stopped at the best station you passed.

Do not stop yet: remember each station's fuel.
Stop only when forced, at the biggest passed station.

Biggest passed station first

Keep a max-heap of the fuel at stations you have passed. Walk through the stations in order, with the target added as the last position.

While the current fuel cannot reach the next position, take the biggest fuel from the heap, add it, and count a stop. If the heap is empty at that point, the target cannot be reached. Otherwise, remember this station's fuel and continue.

Out of reach? pop the biggest fuel and count a stop.
Heap empty: means the answer is −1.
In code
fuel -= distance
heapq.heappush(heap, -tank)
fuel += -heapq.heappop(heap)
Target 50 with 20 starting fuel. Stations at positions 10, 20 and 30 hold 20, 10 and 40 fuel.
20
0
10
1
40
2
i

The starting fuel covers up to position 20. Pass the stations at 10 and 20, remember 20 and 10. Stops 0.

Move 1 of 4
Quick check

You start with 1 fuel, and the target is 100 away. A single station at 10 holds 100. What is the answer?

  1. A−1, you cannot even reach the station
  2. B1
  3. C0
Show the answer

−1, you cannot even reach the station. With 1 fuel you cannot reach position 10, and no earlier station exists.

Your problem

Fewest refuelling stops

A car starts at position 0 with startFuel units of fuel and uses one unit per unit of distance. The target is at position target. You are given stations, where stations[i] = [position, fuel], sorted by position, each strictly between 0 and target. The tank has no limit, and at a station you may take all of its fuel. Return the fewest stops needed to reach the target, or −1 if it cannot be reached. Reaching a station with zero fuel left still counts as reaching it.

Example
target = 100, startFuel = 10, stations = [[10, 60], [20, 30], [30, 30], [60, 40]] → 2

1 ≤ target ≤ 1,000,000,000 · 0 ≤ stations.length ≤ 500 · 1 ≤ position < target · 1 ≤ fuel ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve