# 1801. Number of Orders in the Backlog¶

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public: int getNumberOfBacklogOrders(vector>& orders) { constexpr int kMod = 1'000'000'007; int ans = 0; priority_queue> buysMaxHeap; priority_queue, vector>, greater<>> sellsMinHeap; for (const vector& order : orders) { if (order[2] == 0) buysMaxHeap.push(order); else sellsMinHeap.push(order); while (!buysMaxHeap.empty() && !sellsMinHeap.empty() && buysMaxHeap.top()[0] >= sellsMinHeap.top()[0]) { const int minAmount = min(buysMaxHeap.top()[1], sellsMinHeap.top()[1]); vector buysMaxHeapTop = buysMaxHeap.top(); buysMaxHeap.pop(); buysMaxHeapTop[1] -= minAmount; if (buysMaxHeapTop[1] > 0) buysMaxHeap.push(buysMaxHeapTop); vector sellsMinHeapTop = sellsMinHeap.top(); sellsMinHeap.pop(); sellsMinHeapTop[1] -= minAmount; if (sellsMinHeapTop[1] > 0) sellsMinHeap.push(sellsMinHeapTop); } } while (!buysMaxHeap.empty()) { ans += buysMaxHeap.top()[1], buysMaxHeap.pop(); ans %= kMod; } while (!sellsMinHeap.empty()) { ans += sellsMinHeap.top()[1], sellsMinHeap.pop(); ans %= kMod; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public int getNumberOfBacklogOrders(int[][] orders) { final int kMod = 1_000_000_007; int ans = 0; PriorityQueue buysMaxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]); PriorityQueue sellsMinHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); for (int[] order : orders) { if (order[2] == 0) buysMaxHeap.offer(order); else sellsMinHeap.offer(order); while (!buysMaxHeap.isEmpty() && !sellsMinHeap.isEmpty() && buysMaxHeap.peek()[0] >= sellsMinHeap.peek()[0]) { final int minAmount = Math.min(buysMaxHeap.peek()[1], sellsMinHeap.peek()[1]); buysMaxHeap.peek()[1] -= minAmount; sellsMinHeap.peek()[1] -= minAmount; if (buysMaxHeap.peek()[1] == 0) buysMaxHeap.poll(); if (sellsMinHeap.peek()[1] == 0) sellsMinHeap.poll(); } } while (!buysMaxHeap.isEmpty()) { ans += buysMaxHeap.poll()[1]; ans %= kMod; } while (!sellsMinHeap.isEmpty()) { ans += sellsMinHeap.poll()[1]; ans %= kMod; } return ans; } }