Fuel Stops Along the Way

Hard

A car drives along a straight road to a point distance miles from the start. Its tank holds fuel liters at first, the tank has no upper limit, and every mile burns exactly one liter. There are stations along the road: stations[i] = [pos, amount] is a station at mile pos where the car can take all amount liters at once. Stations are listed by increasing position. Return the smallest number of refueling stops needed to reach the destination, or -1 if it cannot be reached. Arriving at a station or at the destination with an empty tank is fine.

Example 1

distance=50, fuel=15, stations=[[10, 20], [15, 5], [30, 40]] → 2

We cannot reach the station at mile 30 without stopping, so we refuel at mile 10 (+20 liters). At mile 30 we take 40 more liters and easily reach mile 50. One stop is not enough: no station before the last gives enough fuel, and the last one is out of reach on the starting supply.

Example 2

distance=20, fuel=5, stations=[[8, 100]] → -1

Five liters do not even get us to the first station.

Example 3

distance=10, fuel=10, stations=[[3, 1]] → 0

Constraints

1 ≤ distance, fuel ≤ 10⁹
0 ≤ len(stations) ≤ 500
0 < stations[0][0] < stations[1][0] < … < distance
1 ≤ amount ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Dynamic Programming Heap (Priority Queue)

Similar problems

A Round Cake and Two Neighbors Hard The Heaviest Reading Day Hard Growing Capital Project by Project Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard

Input

distance=50, fuel=15, stations=[[10, 20], [15, 5], [30, 40]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 96 tests on the server, hidden ones included.