_871. Question 871.md

871. Question 871

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : March 19, 2026

Last updated : March 19, 2026

---

Related Topics : N/A

Acceptance Rate : Unknown

---

Solutions

• h871 v1 heaps.py
• h871 v2 dp.py

Python

h871 v1 heaps.py

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        hp = []
        curr_fuel = startFuel
        curr_pos = 0
        stations_used = 0

        for pos, fuel in stations :
            curr_fuel -= (pos - curr_pos)
            curr_pos = pos
            
            while curr_fuel < 0 and hp :
                curr_fuel += -heappop(hp)
                stations_used += 1
            
            if curr_fuel < 0 :
                return -1

            heappush(hp, -fuel)
        
        curr_fuel -= (target - curr_pos)
        while curr_fuel < 0 and hp :
            curr_fuel += -heappop(hp)
            stations_used += 1
        
        if curr_fuel < 0 :
            return -1
        return stations_used
        

h871 v2 dp.py

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        dp = [startFuel] + [0] * len(stations)

        for i, (pos, fuel) in enumerate(stations) :
            for j in range(i, -1, -1) :
                if dp[j] >= pos :
                    dp[j + 1] = max(dp[j + 1], dp[j] + fuel)
        
        for i, dist in enumerate(dp) :
            if dist >= target :
                return i
        return -1