1801.md

1801. Number of Orders in the Backlog

Solution 1 (time O(nlog(n)), space O(1))

class Solution(object):
    def getNumberOfBacklogOrders(self, orders):
        """
        :type orders: List[List[int]]
        :rtype: int
        """
        mod = 10 ** 9 + 7
        buy_orders, sell_orders = [], []
        for price, amount, order_type in orders:
            if order_type == 0:
                while amount and sell_orders and sell_orders[0][0] <= price:
                    if sell_orders[0][1] > amount:
                        sell_orders[0][1] -= amount
                        amount = 0
                        break
                    amount -= heappop(sell_orders)[1]
                if amount:
                    heapq.heappush(buy_orders, [-price, amount])
            else:
                while amount and buy_orders and -buy_orders[0][0] >= price:
                    if buy_orders[0][1] > amount:
                        buy_orders[0][1] -= amount
                        amount = 0
                        break
                    amount -= heappop(buy_orders)[1]
                if amount:
                    heapq.heappush(sell_orders, [price, amount])
        return (sum(x for _, x in buy_orders) + sum(x for _, x in sell_orders)) % mod