FunctionRacerProblemsRace

Fewest Charging Stops

EasyGreedyPython, JavaScript, TypeScript, Java, C++

A scooter starts fully charged at position 0 of a straight road and must reach position distance. A full battery takes it at most charge units before it dies, and arriving somewhere with the battery exactly empty is fine. stations lists the positions of charging points in strictly increasing order, all strictly between 0 and distance; stopping at one recharges the battery fully.

Return the fewest charging stops needed to reach distance, or -1 if it cannot be reached at all. The fewest number of stops is unique, so no tie rule is needed.

Example 1

distance 10
charge 4
stations [3,6]
returns 2

From 0 the scooter reaches 4 at most, so it charges at 3; from 3 it reaches 7, so it charges at 6; from 6 it reaches 10.

Example 2

distance 10
charge 10
stations [5]
returns 0

A single charge covers the whole 10 units, so no stop is needed even though a station exists.

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