Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

- Если это заказ на покупку, вы просматриваете заказ на продажу с наименьшей ценой в списке невыполненных заказов. Если цена этого заказа на продажу меньше или равна цене текущего заказа на покупку, они будут сопоставлены и выполнены, и этот заказ на продажу будет удален из списка. В противном случае заказ на покупку добавляется в список невыполненных заказов.
- Если это заказ на продажу, вы просматриваете заказ на покупку с наибольшей ценой в списке невыполненных заказов. Если цена этого заказа на покупку больше или равна цене текущего заказа на продажу, они будут сопоставлены и выполнены, и этот заказ на покупку будет удален из списка. В противном случае заказ на продажу добавляется в список невыполненных заказов.

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

👨‍💻 Алгоритм:

1⃣Обрабатывайте каждый заказ в orders. Для заказа на покупку сравните с самыми дешевыми заказами на продажу в списке и выполняйте их при возможности, иначе добавьте в список.

2⃣Для заказа на продажу сравните с самыми дорогими заказами на покупку в списке и выполняйте их при возможности, иначе добавьте в список.

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        const int MOD = 1'000'000'007;
        priority_queue<pair<int, int>> buyOrders;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> sellOrders;

        for (const auto& order : orders) {
            int price = order[0], amount = order[1], orderType = order[2];
            auto& primaryQueue = orderType == 0 ? sellOrders : buyOrders;
            auto& secondaryQueue = orderType == 0 ? buyOrders : sellOrders;

            while (amount > 0 && !primaryQueue.empty() &&
                  (orderType == 0 ? primaryQueue.top().first <= price : primaryQueue.top().first >= price)) {
                auto [topPrice, topAmount] = primaryQueue.top();
                primaryQueue.pop();
                int executedAmount = min(amount, topAmount);
                amount -= executedAmount;
                if (topAmount > executedAmount)
                    primaryQueue.emplace(topPrice, topAmount - executedAmount);
            }
            if (amount > 0)
                secondaryQueue.emplace(price, amount);
        }

        auto countTotalOrders = [](auto& queue) {
            long long total = 0;
            while (!queue.empty()) {
                total = (total + queue.top().second) % MOD;
                queue.pop();
            }
            return total;
        };

        return (countTotalOrders(buyOrders) + countTotalOrders(sellOrders)) % MOD;
    }
};

Ставь 👍 и забирай 📚 Базу знаний