priority_queue

• Heap

• Priority Queue

• Greedy

  • 1705.Maximum-Number-of-Eaten-Apples (M+)

  • PQ + hashmap

    • 2007. Find Original Array From Doubled Array

Heap

220.Contains-Duplicate-III (M) 295.Find-Median-from-Data-Stream (M) 363.Max-Sum-of-Rectangle-No-Larger-Than-K (H) 352.Data-Stream-as-Disjoint-Intervals (H) 480.Sliding-Window-Median (H) 218.The-Skyline-Problem (H) 699.Falling-Squares (H) 715.Range-Module (H) 729.My-Calendar-I (M) 975.Odd-Even-Jump (H-) 632.Smallest-Range-Covering-Elements-from-K-Lists (H-) 1675.Minimize-Deviation-in-Array (H) 1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers (M) 1348.Tweet-Counts-Per-Frequency (H-) 1606.Find-Servers-That-Handled-Most-Number-of-Requests (M) 1797.Design Authentication Manager (M) 1825.Finding-MK-Average (H) 1912.Design-Movie-Rental-System (M+)

Priority Queue

004.Median-of-Two-Sorted-Arrays (H) 378.Kth-Smallest-Element-in-a-Sorted-Matrix (H-) 373.Find-K-Pairs-with-Smallest-Sums (H) 642.Design-Search-Autocomplete-System (M+) 774.Minimize-Max-Distance-to-Gas-Station (H) 871.Minimum-Number-of-Refueling-Stops (H-) 1057.Campus-Bikes (H-) 1167.Minimum-Cost-to-Connect-Sticks (H-) 1439.Find-the-Kth-Smallest-Sum-of-a-Matrix-With-Sorted-Rows (H-) 1642.Furthest-Building-You-Can-Reach (H-)

Greedy

1705.Maximum-Number-of-Eaten-Apples (M+)

• Greedy with Heap. Always eat apples with earliest rotten date.

  • Error1: Calculate rotten days in a wrong way -_- by just accumulating previous days.

class Solution:
    def eatenApples(self, A, D) -> int:
        if len(D) == 0:
            return 0
                
        currDay = 0
        numEaten = 0
        minHeap = []
        while currDay < len(A) or minHeap: 
            if currDay < len(A) and A[currDay] > 0:                   
                heapq.heappush(minHeap, [currDay + D[currDay], A[currDay]])
        
            while minHeap and (minHeap[0][0] <= currDay or minHeap[0][1] == 0):
                top = heapq.heappop(minHeap)
                
            if minHeap:
                minHeap[0][1] -= 1
                numEaten += 1
            
            currDay += 1
        return numEaten

1792.Maximum-Average-Pass-Ratio (M+) 1801.Number-of-Orders-in-the-Backlog (M) 1882.Process-Tasks-Using-Servers (H) 1942.The-Number-of-the-Smallest-Unoccupied-Chair (M+)

PQ + hashmap

• Python does not have a DS as treemap

2007. Find Original Array From Doubled Array

• https://expl.ai/CUUMUEM