14.9 Minimum Refueling Stops

Minimum refueling stops is a greedy scheduling problem disguised as a travel problem. You are given a target distance, an initial amount of fuel, and a list of fuel stations along the route. The goal is to reach the destination while stopping as few times as possible.

The problem is useful because the greedy choice is not "stop at the nearest station" or "always fill when possible." The correct strategy is more subtle:

Drive as far as possible, and when fuel runs out, refuel from the largest station already passed.

This is a classic example of a delayed greedy decision. Instead of committing immediately, the algorithm postpones the choice until it becomes necessary.

Problem

You start at position 0 and want to reach a target position.

You are given:

• target: destination distance
• startFuel: initial fuel
• stations: fuel stations, each with position and fuel amount

Each unit of fuel moves the car one unit of distance.

Example:

target = 100
startFuel = 10

stations = [
    (10, 60),
    (20, 30),
    (30, 30),
    (60, 40)
]

Goal:

Return the minimum number of refueling stops needed to reach the target.

First Intuition

A naive rule is:

Stop whenever possible.

This works, but it may stop too often.

Another naive rule is:

Stop at the nearest reachable station.

This also fails because nearby stations may provide little fuel while larger stations slightly farther away may be more useful.

The problem asks for minimum stops, so each stop should contribute as much useful reach as possible.

Greedy Insight

Suppose you can currently reach position 30.

Along the way, you passed several stations:

Station	Fuel
10	60
20	30
30	30

If you now need more fuel, which station should you pretend you had stopped at?

The best choice is the station with the largest fuel amount.

This gives the maximum possible extension for one additional stop.

The algorithm therefore uses a max-heap:

• Add every reachable station to the heap.
• When you cannot go farther, extract the largest fuel amount.
• Count one refueling stop.
• Continue.

The key idea is that the exact physical moment of refueling can be viewed retroactively. If a station has already been passed, choosing it later is equivalent to having stopped there earlier.

Algorithm

Maintain:

• fuel: farthest distance currently reachable
• i: index of the next station not yet considered
• heap: max-heap of fuel amounts from stations already reachable
• stops: number of refueling stops used

Procedure:

while fuel < target:
    while next station is reachable:
        push its fuel into max-heap

    if heap is empty:
        return impossible

    fuel += largest fuel from heap
    stops += 1

return stops

Example Walkthrough

Input:

target = 100
startFuel = 10
stations = [
    (10, 60),
    (20, 30),
    (30, 30),
    (60, 40)
]

Initial reach:

fuel = 10

Reachable stations:

(10, 60)

Heap:

[60]

Fuel is less than target, so refuel from the largest passed station:

fuel = 10 + 60 = 70
stops = 1

Now reachable stations:

(20, 30)
(30, 30)
(60, 40)

Heap:

[40, 30, 30]

Fuel is still less than target, so refuel from the largest passed station:

fuel = 70 + 40 = 110
stops = 2

Now:

fuel >= target

Answer:

2

The selected stops are effectively at positions 10 and 60.

Why This Greedy Choice Works

At any point where the current fuel cannot reach the next required point, the algorithm must add fuel from one of the stations already passed.

No future station is available because it has not been reached yet.

Among all passed stations, choosing the largest fuel amount gives the farthest possible new reach using one stop.

Any solution that chooses a smaller passed station can be improved by replacing that choice with the larger one.

This replacement:

• uses the same number of stops
• remains feasible
• reaches at least as far

Therefore the largest passed station is always a safe greedy choice.

Exchange Argument

Suppose an optimal solution reaches a point where it needs one more stop and chooses a passed station with fuel:

x

But another passed station has fuel:

y

where:

y > x

Exchange the choice.

Use station y instead of station x.

The number of stops remains unchanged.

Reach increases by at least as much as before.

No future option becomes worse, because greater reach can only expose more stations.

Thus an optimal solution exists that chooses the largest available fuel amount.

This proves the greedy choice.

Why the Heap Is Necessary

At each stage, the algorithm needs the largest fuel amount among reachable but unused stations.

A max-heap supports:

Operation	Cost
Insert reachable station	O(log n)
Extract largest fuel	O(log n)

Without a heap, each refueling decision may require scanning all previously seen stations, producing slower code.

Go Implementation

Go’s standard heap is a min-heap, so we store negative fuel values or define a reversed comparator. A custom max-heap is usually cleaner.

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

Now implement the algorithm:

type Station struct {
	Position int
	Fuel     int
}

func MinRefuelStops(target int, startFuel int, stations []Station) int {
	reach := startFuel
	stops := 0
	i := 0

	h := &MaxHeap{}
	heap.Init(h)

	for reach < target {
		for i < len(stations) && stations[i].Position <= reach {
			heap.Push(h, stations[i].Fuel)
			i++
		}

		if h.Len() == 0 {
			return -1
		}

		reach += heap.Pop(h).(int)
		stops++
	}

	return stops
}

This implementation assumes stations is sorted by position. If the input does not guarantee sorting, sort first.

sort.Slice(stations, func(i, j int) bool {
	return stations[i].Position < stations[j].Position
})

Complexity Analysis

Let n be the number of stations.

Sorting, if needed:

O(n log n)

Each station is pushed into the heap once:

O(n log n)

Each selected station is popped at most once:

O(n log n)

Total:

O(n log n)

Space:

O(n)

for the heap.

Common Mistakes

Refueling Immediately at Every Station

This may produce a feasible route, but not the minimum number of stops.

The algorithm should delay the decision until fuel is needed.

Choosing the Nearest Station

The nearest station may provide little fuel.

Minimum stops depends on reach extension, not distance alone.

Ignoring Passed Stations

A station already passed still matters in the algorithm’s model. The heap records stations that could have been used.

Forgetting to Add All Reachable Stations

Before refueling, every station within current reach must be inserted into the heap. Otherwise the algorithm may miss the best available choice.

Assuming Future Stations Are Available

Only stations already reachable can be used. A larger future station is irrelevant until the current reach gets there.

Relationship to Other Greedy Problems

Interval scheduling commits immediately:

Choose the earliest finishing interval.

Fractional knapsack commits immediately:

Take the highest-density item.

Minimum refueling stops delays commitment:

When forced to refuel, choose the largest station already passed.

This delayed choice pattern is common in greedy algorithms. It appears when decisions are only necessary at constraint boundaries.

Takeaway

Minimum refueling stops is solved by driving as far as possible and using a max-heap to remember fuel from all reachable stations. When more fuel becomes necessary, the algorithm chooses the largest available fuel amount among stations already passed. This greedy choice is optimal because replacing any smaller chosen station with a larger passed station preserves feasibility and never reduces future options. The result is an efficient O(n log n) algorithm with a clean exchange argument and a practical implementation pattern.