1801. Number of Orders in the Backlog - Beats 86 %
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom heapq import heapify, heappop, heappush\nclass Solution:\n    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n        bq = [] # contains (-price, amount), maxHeap\n        sq = [] # contains (price, amount), minHeap\n        heapify(bq)\n        heapify(sq)\n        for [price, amount, oType] in orders:\n            if oType == 0:\n                # check if sq exists, amount > 0 and seller with less than price exists\n                while len(sq) > 0 and sq[0][0] <= price and amount > 0:\n                    [existingPrice, existingAmount] = heappop(sq)\n                    reaminingAmount = existingAmount - amount\n                    amount = amount - existingAmount\n                    # if seller still exists after fulfilling order then add the remaing to sell queue\n                    if(reaminingAmount) > 0:\n                        heappush(sq, (existingPrice, reaminingAmount))\n                # if no sq or no seller for price or incomplete order then add backlog in buy queue\n                if amount > 0:\n                    heappush(bq, (-price, amount))\n            else:\n                # check if bq exists, amount > 0 and buyer with greater than price exists\n                while len(bq) > 0 and -bq[0][0] >= price and amount > 0:\n                    [existingPrice, existingAmount] = heappop(bq)\n                    reaminingAmount = existingAmount - amount\n                    amount = amount - existingAmount\n                    # if buyer still exists after fulfilling order then add the remaining to buy queue\n                    if(reaminingAmount) > 0:\n                        heappush(bq, (existingPrice, reaminingAmount))\n                # if no bq or no buyer for price or incomplete order then add backlog in sell queue\n                if amount > 0:\n                    heappush(sq, (price, amount))\n        res = 0\n        while len(sq) > 0:\n            res += heappop(sq)[1]\n        while len(bq) > 0:\n            res += heappop(bq)[1]\n        return res % (10 ** 9 + 7)\n```
['Heap (Priority Queue)', 'Python3']