Skip to main content

Minimum Fuel Stops to Destination

easy
GreedyHeapArrayGreedy IntervalTop K Heap
Asked atAmazonGoogleMicrosoft

Problem Description

You are driving along a straight highway of total length `roadLength` miles. Your car starts with `startFuel` units of fuel. Along the road there are `n` fuel stations, each described by `[position, fuelAmount]`, where `position` is the distance from the start and `fuelAmount` is how much fuel you can pick up there.

Your car consumes exactly 1 unit of fuel per mile. You want to reach the destination (at mile `roadLength`) stopping at the **fewest** number of stations possible.

Return the minimum number of fuel stops needed to reach the destination, or `-1` if it is impossible.

**Example 1:**
```
Input: roadLength = 100, startFuel = 10, stations = [[10,60],[20,30],[30,40],[60,40]]
Output: 2
Explanation: Stop at station 0 (pick up 60), then stop at station 3 (pick up 40). Total stops = 2.
```

**Example 2:**
```
Input: roadLength = 50, startFuel = 5, stations = [[25,10]]
Output: -1
Explanation: Cannot reach mile 25 with only 5 units of fuel.
```

Constraints

  • 1 <= roadLength <= 10^9
  • 0 <= startFuel <= roadLength
  • 0 <= stations.length <= 500
  • 0 < stations[i][0] < roadLength
  • 1 <= stations[i][1] <= 10^9
  • Stations are given in strictly increasing order of position.

Follow-up

What if each station has a limit on how many times you can refuel (e.g. at most once per visit)? Extend the solution to handle a cost per stop that varies by station.

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.