LC-0871 Hard LeetCode

871. Minimum Number of Refueling Stops

Array Dynamic Programming Greedy Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 41% Topics: Array, Dynamic Programming, Greedy, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

import heapq


class Solution(object):
    def minRefuelStops(self, target, startFuel, stations):
        """
        :type target: int
        :type startFuel: int
        :type stations: List[List[int]]
        :rtype: int
        """
        max_heap = []
        stations.append((target, float("inf")))

        result = prev = 0
        for location, capacity in stations:
            startFuel -= location - prev
            while max_heap and startFuel < 0:
                startFuel += -heapq.heappop(max_heap)
                result += 1
            if startFuel < 0:
                return -1
            heapq.heappush(max_heap, -capacity)
            prev = location

        return result

Solution from kamyu104/LeetCode-Solutions · MIT