FunctionRacerProblemsRace

Fewest Fuel Depot Stops

HardGreedyPython, JavaScript, TypeScript, Java, C++

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

target 100
fuel 10
depots [[10,60],[20,30],[30,30],[60,40]]
returns 2

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

target 100
fuel 1
depots [[10,100]]
returns -1

The truck can only reach position 1 and the first depot sits at 10.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems