1801. Number of Orders in the Backlog

leetcode medium

#array#csharp#heap#leetcode#math#medium#queue

Task

Дан двумерный целочисленный массив

orders

, где каждый элемент

orders[i] = [pricei, amounti, orderTypei]

обозначает, что было размещено

amounti

заказов типа

orderTypei

по цене

pricei

. Тип заказа

orderTypei

может быть:

, если это партия заказов на покупку, или

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

Обратите внимание, что

orders[i]

представляет собой партию из

amounti

независимых заказов с одинаковой ценой и типом. Все заказы, представленные

orders[i]

, будут размещены перед всеми заказами, представленными

orders[i+1]

для всех допустимых

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

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

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

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

10^9 + 7

Пример:

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

Output: 6

C# solution

matched/original

public class Solution {
    public int GetNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1_000_000_007;
        var buyOrders = new PriorityQueue<(int price, int amount), int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        var sellOrders = new PriorityQueue<(int price, int amount), int>();
        foreach (var order in orders) {
            int price = order[0], amount = order[1], orderType = order[2];
            var primaryQueue = orderType == 0 ? sellOrders : buyOrders;
            var secondaryQueue = orderType == 0 ? buyOrders : sellOrders;
            bool isBuyOrder = orderType == 0;
            while (amount > 0 && primaryQueue.Count > 0 && 
                   (isBuyOrder ? primaryQueue.Peek().price <= price : primaryQueue.Peek().price >= price)) {
                var topOrder = primaryQueue.Dequeue();
                int executedAmount = Math.Min(amount, topOrder.amount);
                amount -= executedAmount;
                if (topOrder.amount > executedAmount) {
                    primaryQueue.Enqueue((topOrder.price, topOrder.amount - executedAmount), topOrder.price);
                }
            }
            if (amount > 0) {
                secondaryQueue.Enqueue((price, amount), price);
            }
        }
        return (int)((SumOrders(buyOrders) + SumOrders(sellOrders)) % MOD);
    }
    private long SumOrders(PriorityQueue<(int price, int amount), int> queue) {
        long total = 0;
        while (queue.Count > 0) {
            total += queue.Dequeue().amount;
        }
        return total;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int GetNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1_000_000_007;
        var buyOrders = new PriorityQueue<(int price, int amount), int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        var sellOrders = new PriorityQueue<(int price, int amount), int>();
        foreach (var order in orders) {
            int price = order[0], amount = order[1], orderType = order[2];
            var primaryQueue = orderType == 0 ? sellOrders : buyOrders;
            var secondaryQueue = orderType == 0 ? buyOrders : sellOrders;
            bool isBuyOrder = orderType == 0;
            while (amount > 0 && primaryQueue.size() > 0 && 
                   (isBuyOrder ? primaryQueue.Peek().price <= price : primaryQueue.Peek().price >= price)) {
                var topOrder = primaryQueue.Dequeue();
                int executedAmount = min(amount, topOrder.amount);
                amount -= executedAmount;
                if (topOrder.amount > executedAmount) {
                    primaryQueue.Enqueue((topOrder.price, topOrder.amount - executedAmount), topOrder.price);
                }
            }
            if (amount > 0) {
                secondaryQueue.Enqueue((price, amount), price);
            }
        }
        return (int)((SumOrders(buyOrders) + SumOrders(sellOrders)) % MOD);
    }
    private long SumOrders(PriorityQueue<(int price, int amount), int> queue) {
        long total = 0;
        while (queue.size() > 0) {
            total += queue.Dequeue().amount;
        }
        return total;
    }
}

Java solution

matched/original

class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1_000_000_007;
        PriorityQueue<int[]> buyOrders = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        PriorityQueue<int[]> sellOrders = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int[] order : orders) {
            int price = order[0], amount = order[1], orderType = order[2];

            PriorityQueue<int[]> targetQueue = orderType == 0 ? sellOrders : buyOrders;
            PriorityQueue<int[]> sourceQueue = orderType == 0 ? buyOrders : sellOrders;
            boolean isBuyOrder = orderType == 0;

            while (amount > 0 && !targetQueue.isEmpty() && 
                   (isBuyOrder ? targetQueue.peek()[0] <= price : targetQueue.peek()[0] >= price)) {
                int[] topOrder = targetQueue.poll();
                int executedAmount = Math.min(amount, topOrder[1]);
                amount -= executedAmount;
                if (topOrder[1] > executedAmount) {
                    targetQueue.offer(new int[]{topOrder[0], topOrder[1] - executedAmount});
                }
            }
            if (amount > 0) {
                sourceQueue.offer(new int[]{price, amount});
            }
        }

        return (int) (streamQueue(buyOrders, MOD) + streamQueue(sellOrders, MOD)) % MOD;
    }

    private long streamQueue(PriorityQueue<int[]> queue, int mod) {
        long total = 0;
        while (!queue.isEmpty()) {
            total = (total + queue.poll()[1]) % mod;
        }
        return total;
    }
}

Python solution

matched/original

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buyOrders, sellOrders = [], []
        MOD = 1_000_000_007

        for price, amount, orderType in orders:
            if orderType == 0:
                while amount > 0 and sellOrders and sellOrders[0][0] <= price:
                    sellOrder = heapq.heappop(sellOrders)
                    executedAmount = min(amount, sellOrder[1])
                    amount -= executedAmount
                    if sellOrder[1] > executedAmount:
                        heapq.heappush(sellOrders, (sellOrder[0], sellOrder[1] - executedAmount))
                if amount > 0:
                    heapq.heappush(buyOrders, (-price, amount))
            else:
                while amount > 0 and buyOrders and -buyOrders[0][0] >= price:
                    buyOrder = heapq.heappop(buyOrders)
                    executedAmount = min(amount, buyOrder[1])
                    amount -= executedAmount
                    if buyOrder[1] > executedAmount:
                        heapq.heappush(buyOrders, (buyOrder[0], buyOrder[1] - executedAmount))
                if amount > 0:
                    heapq.heappush(sellOrders, (price, amount))

        return sum(amount for _, amount in buyOrders + sellOrders) % MOD

Explanation

Algorithm

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

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

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

😎