5710. 积压订单中的订单总数

算法

最大堆+最小堆 $O(n log n)$

• 按照题目意思模拟即可
• 每次遇到 buy 都需要找到最低的 sell，因此 sell 用最小堆存储，使用 pair，第一个关键字是订单价格用来排序，第二个关键之是订单数量
• 同理，buy 用最大堆存储
• 每次遇到新的 buy 订单，去 sell 中执行对应的更新操作；反之同理。
• 最后，两个堆中剩余的订单总数就是答案

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int P = 1e9 + 7;
class Solution {
   public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        priority_queue<PII> buy;
        priority_queue<PII, vector<PII>, greater<PII>> sell;
        for (auto& o : orders) {
            // buy
            if (o[2] == 0) {
                while (o[1] && sell.size() && sell.top().first <= o[0]) {
                    if (sell.top().second <= o[1]) {
                        o[1] -= sell.top().second;
                        sell.pop();
                    } else {
                        auto now = sell.top();
                        sell.pop();
                        now.second -= o[1];
                        sell.push(now);
                        o[1] = 0;
                    }
                }
                if (o[1]) {
                    buy.push({o[0], o[1]});
                }
            } else {
                // sell
                while (o[1] && buy.size() && buy.top().first >= o[0]) {
                    if (buy.top().second <= o[1]) {
                        o[1] -= buy.top().second;
                        buy.pop();
                    } else {
                        auto now = buy.top();
                        buy.pop();
                        now.second -= o[1];
                        buy.push(now);
                        o[1] = 0;
                    }
                }
                if (o[1]) {
                    sell.push({o[0], o[1]});
                }
            }
            // cout << buy.size() << " " << sell.size() << endl;
        }
        int ans = 0;
        while (sell.size()) {
            ans = (ans + sell.top().second) % P;
            sell.pop();
        }
        while (buy.size()) {
            ans = (ans + buy.top().second) % P;
            buy.pop();
        }
        return ans;
    }
};