23.08.17 Today’s Leetcode

871. Minimum Number of Refueling Stops (hard)

failed with DFS

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

        p = {}
        p[0] = startFuel
        for station in stations:
            pos, fuel = station
            p[pos] = fuel
        
        print(p)

        res = math.inf

        @cache
        def dfs(cur, fuel, count):
            nonlocal res, target
            if cur > target:
                return
            if cur == target:
                # print("done", count)
                res = min(res, count)
                return 
            if cur not in p:
                return
            fuel += p[cur]
            # print(cur, fuel)
            for use in range(1, fuel + 1):
                dfs(cur + use, fuel - use, count + 1)

        dfs(0, 0, -1)
        return -1 if res == math.inf else res

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target: return 0
        h, f, count, xCar = [], startFuel, 0, 0
        for x, supply in stations + [[target,0]]:
            f -= x - xCar
            xCar = x
            while f < 0:
                    if not h: return -1
                    f -= heappop(h)
                    count += 1
            if x + f >= target: 
                return count
            heappush(h, -supply)
        return -1