Fewest Fuel Stops on the Mumbai–Delhi Run
A truck drives the Mumbai–Delhi highway, a distance of `target` km. It starts with `startFuel` litres, burning one litre per km. Fuel stations sit along the route at known positions, each offering a fixed number of litres. Minimise the number of refuelling stops to reach Delhi.
Problem
Given target distance, startFuel, and stations[] where stations[i] = [position_km, litres], return the minimum number of refuelling stops needed to reach the target. If unreachable, return -1. The truck may stop at any station it can reach and take all of its fuel.
Input
Integers target and startFuel, then n station pairs [position, litres] sorted by position.
Output
Minimum number of stops, or -1 if the destination cannot be reached.
Constraints
- 1 ≤ target ≤ 1e9
- 0 ≤ startFuel ≤ 1e9
- 0 ≤ n ≤ 500
- 0 < position < target
- 0 ≤ litres ≤ 1e9
- Stations are given in increasing position order.
Examples
Example 1
Input
target=100 startFuel=10 [[10,60],[20,30],[30,30],[60,40]]
Output
2
Drive to km10 (fuel 0+60), then to km60 (fuel 50-... ) — greedily taking the two largest reachable tanks reaches 100 in 2 stops.
Example 2
Input
target=100 startFuel=1 [[10,100]]
Output
-1
Only 1 litre — cannot even reach the station at km10.