871.md

871 Minimum Number of Refueling Stops

Description

link

---

Solution 1 : HEAP

pq : store all stations' fuel liters that current can reach, pop the max number and refueling (update cur), record times (res)

heapq.heappush() the opposite number for the maximum piority quene

---

Code 1

Complexity T : O(nlog(n)) M : O(log(n))

class Solution:
    def minRefuelStops(self, target, startFuel, stations):
        """
        :type target: int
        :type startFuel: int
        :type stations: List[List[int]]
        :rtype: int
        """
        pq = []
        i = res = 0
        cur = startFuel
        
        while cur < target:
            while i < len(stations) and stations[i][0] <= cur:
                heapq.heappush(pq, - stations[i][1])
                i += 1
            if not pq:
                return -1
            max_g = - heapq.heappop(pq)
            cur += max_g
            res += 1
            
        return res

---

Solution 2 : DP

dp[i] : after i times the car can reach maximum distance

Recursive : dp[i + 1] = max(dp[i + 1], dp[i] + station[i][1]) if dp[i] > stations[i + 1][0]

---

Code 2

Complexity T : O(n^2) M : O(n)

class Solution:
    def minRefuelStops(self, target, startFuel, stations):
        """
        :type target: int
        :type startFuel: int
        :type stations: List[List[int]]
        :rtype: int
        """
        dp = [0 for _ in range(len(stations) + 1)]
        
        # dp[i + 1] = max(dp[i + 1], dp[i] + station[i][1]) if dp[i] > stations[i + 1][0]
        
        dp[0] = startFuel
        
        for i in range(len(stations)):
            for j in range(i, -1, -1):
                if dp[j] >= stations[i][0]:
                    dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1])
                
        for i, d in enumerate(dp):
            if d >= target:
                return i
            
        return -1