# 1801. Number of Orders in the Backlog
###### tags: `Leetcode` `Medium` `Priority Queue`
Link: https://leetcode.com/problems/number-of-orders-in-the-backlog/
## 思路 $O(NlogN)$ $O(N)$
建两个queue buy和sell buy按照price从大到小排 sell按照price从小到大排
每次新加入一个order 都跑回圈清除掉所有使得```sell.peek()[0]<buy.peek()[0]```的pairs
## Code

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        sell, buy = [], []
        for p, a, t in orders:
            if t == 0:
                heapq.heappush(buy, [-p, a])
            else:
                heapq.heappush(sell, [p, a])
            while sell and buy and sell[0][0] <= -buy[0][0]:
                k = min(buy[0][1], sell[0][1])
                buy[0][1] -= k
                sell[0][1] -= k
                if buy[0][1] == 0: heapq.heappop(buy)
                if sell[0][1] == 0: heapq.heappop(sell)
        return sum(a for p, a in buy + sell) % (10**9 + 7)

class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        Queue<int[]> buy = new PriorityQueue<>((a,b)->(b[0]-a[0]));
        Queue<int[]> sell = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        for(int[] order:orders){
            if(order[2]==0) buy.add(order);
            else sell.add(order);
            while(!sell.isEmpty() && !buy.isEmpty() && sell.peek()[0]<=buy.peek()[0]){
                int k = Math.min(buy.peek()[1], sell.peek()[1]);
                buy.peek()[1] -= k;
                sell.peek()[1] -= k;
                if (buy.peek()[1] == 0) buy.poll();
                if (sell.peek()[1] == 0) sell.poll();
            }
        }
        int res = 0, mod = 1000000007;
        for(int[] b:buy){
            res = (res+b[1])%mod;
        }
        for(int[] s:sell){
            res = (res+s[1])%mod;
        }
        return res;
    }
}