number-of-orders-in-the-backlog.cpp

// Time:  O(nlogn)
// Space: O(n)

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        static const int MOD = 1e9 + 7;

        priority_queue<vector<int>> buy;  // max_heap
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> sell;  // min_heap
        for (const auto& o : orders) {
            if (o[2] == 0) {
                buy.emplace(o);
            } else {
                sell.emplace(o);
            }
            while (!empty(buy) && !empty(sell) && sell.top()[0] <= buy.top()[0]) {
                int k = min(buy.top()[1], sell.top()[1]);
                auto tmp = buy.top(); buy.pop();
                tmp[1] -= k;
                if (tmp[1]) {
                    buy.emplace(tmp);
                }
                tmp = sell.top(); sell.pop();
                tmp[1] -= k;
                if (tmp[1]) {
                    sell.emplace(tmp);
                }
            }

        }
        int result = 0;
        while (!empty(buy)) {
            result = (result + buy.top()[1]) % MOD; buy.pop();
        }
        while (!empty(sell)) {
            result = (result + sell.top()[1]) % MOD; sell.pop();
        }
        return result;
    }
};