[LeetCode] 871. Minimum Number of Refueling Stops

 Problem: https://leetcode.com/problems/minimum-number-of-refueling-stops/

 Record the amount of gas can get from stations within current maximum distance.

When cannot reach to next station / the target position,  refuel with the maximum amount of gas from the visited gas station to extend the maximum distance can reach and increase refuel count. In the end, check the maximum distance exceeds the target position.

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        maxSoFar = startFuel
        heap = []
        
        i = 0
        refuel = 0
                
        while maxSoFar < target:
            while i < len(stations) and stations[i][0] <= maxSoFar:
                # save gas of station i in heap
                heapq.heappush(heap, -stations[i][1])
                i += 1
            
            if heap:
                # refuel with the maximum amount of gas from visited stations
                maxSoFar += -1 * heapq.heappop(heap)
                refuel += 1
            else:
                break
      
        return refuel if maxSoFar >= target else -1