#871

Minimum Number of Refueling Stops

master · 1665 · lc hard +32 · verified · 41.1% accepted · 4,864 likes · top 21%

Description

A car sets out from a starting position toward a destination target miles to the east. Along the route, gas stations are represented by stations where stations[i] = [positioni, fueli] gives the mile marker and available fuel (in liters) at each station.

The car begins with startFuel liters of fuel and consumes one liter per mile. At any station, the car may stop and take all available fuel. The tank has unlimited capacity.

Return the minimum number of refueling stops required to reach the destination. If it is impossible, return -1.

A car that arrives at a station or the destination with exactly 0 fuel is still considered to have reached it.

Example 1:

Input: target = 1, startFuel = 1, stations = []

Output: 0

Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]

Output: -1

Explanation: We can not reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]

Output: 2

Explanation: We start with 10 liters of fuel.

We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas.

Then, we drive from position 10 to position 60 (expending 50 liters of fuel),

and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target.

We made 2 refueling stops along the way, so we return 2.

Code

1

2

3

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int: