900. Fewest Stops to Reach the End

A van drives from position 0 to position target along a straight road, burning one litre of fuel per unit of distance. It starts with start litres and the tank has no size limit.

There are n fuel stations. Station j sits at position pos and holds fuel litres; stopping there transfers ALL of its fuel into the tank. Stations are given in any order.

Print the fewest stops needed to reach target, or -1 if it cannot be reached.

target 100, start 10, stations (10,60) (20,30) (30,30) (60,40) -> 2 target 100, start 1, no stations -> -1 target 100, start 100, station (10,100) -> 0 target 50, start 10, stations (10,10) (20,10) (30,10) -> -1

The first row: with 10 litres the van reaches position 10. Taking the 60 there gives it 70, enough to reach position 70, which passes the stations at 20, 30 and 60. Taking the 40 from the station at 60 gives 110 in total, which reaches 100. Two stops.

The last row: 10 litres reach position 10, the station there gives 10 more for a range of 20, the station at 20 gives another 10 for a range of 30, the one at 30 gives 10 for a range of 40, and 40 is short of 50 with nothing left.

## What most people try first

Stopping at every station. That reaches the target whenever it is reachable at all, and it does not MINIMISE the stops, which is the question.

Stopping at the nearest station whenever fuel runs low. Wrong, because a stop is a stop whatever the station holds. With target = 20, start = 10 and stations (5, 1) and (10, 10), the nearest-first rule stops at 5 for one litre, reaching 11, and then has to stop again at 10, for two stops. Going straight past the small station to the one at 10 arrives with one stop.

Taking the biggest station overall. It may be past the van's range.

## Deciding in the past

The move that makes this tractable is to STOP DECIDING IN ADVANCE. Drive as far as the current fuel allows, collecting stations into a max-heap as you pass them WITHOUT taking their fuel. When the van cannot go further, reach back and take the largest station it has already passed.

sort the stations by position h = empty max-heap of fuel amounts reach = start, stops = 0, j = 0 while reach < target: while j < n and pos[j] <= reach: push fuel[j]; j = j + 1 if h is empty: print -1 and stop reach = reach + pop(h) stops = stops + 1 print stops

Note that reach counts the total distance the van could cover from position 0, not the fuel in the tank at some moment. Because fuel burns at one litre per unit and is never wasted, those two views agree, and the first is far easier to maintain.

## Why taking the largest passed station is optimal

Claim: after k stops, the algorithm's reach is at least that of any other plan with k stops.

It holds at k = 0, both being start. Suppose it holds at k. Any plan's (k+1)th stop is at a station within its own reach, which by the induction hypothesis is within the algorithm's reach too, so that station is already in the algorithm's heap. The algorithm takes the LARGEST station in its heap, so the fuel it adds is at least what the other plan adds, and its reach stays at least as large.

So if any plan reaches the target in k stops, the algorithm does too, and since the algorithm stops as soon as it arrives, it uses the fewest.

## Why taking the fuel late is not cheating

A station's fuel is available from the moment the van passes it, and taking it later has exactly the same effect on the total distance as taking it at the time. Nothing about the van's position depends on WHEN the fuel entered the tank, only on how much has entered by the end. That is what licenses the retroactive decision, and it is a property of this problem rather than of greedy algorithms in general.

## The boundary that breaks a careless implementation

A station exactly at the current reach. pos[j] <= reach must use the =: the van arrives with an empty tank, which the statement allows, and the station is reachable. The example with stations at 5 and 6 turning on that comparison is in the tests.

Stations beyond the target. The constraints exclude them, but the loop would naturally collect them anyway. It does no harm here, since the loop stops as soon as reach >= target.

Reaching the target with no stops at all. The while must be tested before the first iteration or start >= target answers 1 instead of 0.

## What is NOT an overflow here

target and start are at most 10^9, and reach grows past target only on the final step, so it never exceeds target + 10^9, that is 2 * 10^9. The largest signed 32-bit integer is 2147483647, so even that fits. There is genuinely no overflow in this problem, and claiming one would be teaching a reflex rather than a fact.

## Related problems

Problem 761 asks the reverse question about the same kind of trip: the smallest TANK capacity that survives, with a stop budget and a full refill at every stop. Because the answer there is a capacity and the feasibility test is monotone in it, that one is a binary search with a forward greedy inside. Here the tank is unlimited, the stations carry fixed amounts, and the answer is the stop count, so the heap is what is left.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ target ≤ 1000000000` - `0 ≤ start ≤ 1000000000` - `0 ≤ n ≤ 200000` - `0 < pos < target` - `1 ≤ fuel ≤ 1000000000`