leetcode：871. Minimum refueling times [Pat has done before + maximum stacking + greed]

analysis

Be careful , Gas stations are along the way , therefore target It must be on the right side of all gas stations
then , The effect of oil is cumulative , The root jumping game is different , You can't walk for a while and be greedy
We should be greedy with the largest amount of refueling before the maintenance of a large root pile
Thought is , Go somewhere , If the oil after arriving is negative , Then find the maximum value stored in the gas station before and add it , Calculate once
If you can't get everything before you add it, it's cool
Then put the current gas station into the big pile （ Reward ）, And update the previous point prev
Be careful ,target It's the last one curr, Count it up

Ac code

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        #  The effect of refueling is cumulative 
        #  So use a big pile , Take the biggest refueling every time to be greedy （ Big root pile ）
        #  If you can't get to the current point after taking it , return -1

        ans, nowFuel, prev, pq = 0, startFuel, 0, []
        stations.sort()
        n = len(stations)

        #  More than a target The location of 
        #  Right gas station along the way , therefore target It must be on the far right 
        for i in range(n + 1):
            #  The current location to go 
            curr = stations[i][0] if i < n else target
            nowFuel -= curr - prev
            #  Not enough oil , Greedy refueling 
            while nowFuel < 0 and pq:
                nowFuel += -heappop(pq)
                ans += 1
            
            #  After adding, you can't go 
            if nowFuel < 0:
                return -1
            
            #  If you can go to , Put it into the big pile 
            if i < n:
                heappush(pq, -stations[i][1])
                #  to update prev
                prev = curr
        
        return ans

summary

greedy + Big root pile
very classic