Fewest Fuel Depot Stops
A truck starts at position 0 with fuel litres in a tank of unlimited size and must reach position target on a straight road; every unit of distance burns one litre. Each item of depots is [position, litres]: a depot at that position where a stop adds litres to the tank. Positions are strictly increasing and strictly between 0 and target. The truck can only stop at a depot it reaches with fuel to spare or exactly empty, and reaching target with an empty tank counts as arriving.
Return the fewest depot stops needed to reach target, or -1 if it is impossible. The fewest number of stops is unique, so no tie rule is needed.
Example 1
With 10 litres the truck reaches the depot at 10 and takes 60 litres, which carries it past the depots at 20, 30 and 60; stopping at 60 for 40 more litres reaches 100. Two stops, and one stop is never enough.
Example 2
The truck can only reach position 1 and the first depot sits at 10.
Constraints
1 <= target <= 10000 <= fuel <= 10000 <= len(depots) <= 1000 < position < target, strictly increasing1 <= litres <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.