1801. Number of Orders in the Backlog - cocoder39/coco39_LC GitHub Wiki

1801. Number of Orders in the Backlog

time complexity: N * logN

1. suppose a buy order and b sell order where a + b = N
2. to insert into pq, a*loga + b * logb < a * log N + b * log N = N * log N
3. each mach eliminates one entry in sell queue or buy queue so amortized time complexity of removing all elements is N * log N
4. overall time complexity is N * log n

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buy_backlog = [] # max heap
        sell_backlog = [] # min heap

        for price, amount, orderType in orders:
            if orderType == 0: # buy order
                heapq.heappush(buy_backlog, [-price, amount])
            else:
                heapq.heappush(sell_backlog, [price, amount])
            
            while buy_backlog and sell_backlog and -buy_backlog[0][0] >= sell_backlog[0][0]:
                sold = min(buy_backlog[0][1], sell_backlog[0][1])
                buy_backlog[0][1] -= sold
                if buy_backlog[0][1] == 0:
                    heapq.heappop(buy_backlog)
                sell_backlog[0][1] -= sold
                if sell_backlog[0][1] == 0:
                    heapq.heappop(sell_backlog)
        
        res = 0
        MOD = 10**9 + 7
        for _, amount in buy_backlog:
            res += amount
            res %= MOD
        for _, amount in sell_backlog:
            res += amount
            res %= MOD
        return res