Number Of Orders In The Backlog - Leetcode Solution

Problem Statement:

You want to determine the maximum number of orders that can be completed from the existing backlog. The backlog consists of two types of orders: sell orders and buy orders.

Whenever an order is placed, it is marked as either a sell order or a buy order. A sell order is an order to sell a certain quantity of a certain item at a certain price. A buy order is an order to buy a certain quantity of a certain item at a certain price.

A sell order can only be completed if there is a buy order to match it with (i.e., at the same price or a higher price). Similarly, a buy order can only be completed if there is a sell order to match it with (i.e., at the same price or a lower price).

For example, suppose there are currently three orders in the backlog:

Sell: 10 @ 5 Buy: 8 @ 6 Sell: 3 @ 7

In this example, the first sell order can be completed with the second buy order, and the second sell order can be completed with the third buy order. The total number of orders that can be completed is therefore two.

Write a function to determine the maximum number of orders that can be completed from the backlog.

Function signature: int maxCompletedOrders(int numOrders, vector<int> orderType, vector<int> orderQuantity, vector<int> orderPrice);

Constraints:

1 <= numOrders <= 105

0 <= orderType[i] <= 1, where 0 represents a buy order and 1 represents a sell order.

1 <= orderQuantity[i], orderPrice[i] <= 109

The input vector should have the same length as numOrders.

Solution:

We can use a priority queue to keep track of the buy and sell orders. For buys, we can store them in descending order according to their price, so that the highest-priced buy is at the top of the queue and can be matched with the lowest-priced sell. For sells, we can store them in ascending order according to their price, so that the lowest-priced sell is at the top of the queue and can be matched with the highest-priced buy.

We can iterate through the orders and add them to the appropriate queue. Whenever we add an order, we check to see if it can be immediately matched with an order in the opposite queue. If it can be, we remove the matched orders from both queues and increment our completed orders count. We continue adding orders and checking for matches until we can no longer find any matches.

At the end, we return the total number of completed orders.

Here is the code:

int maxCompletedOrders(int numOrders, vector<int> orderType, vector<int> orderQuantity, vector<int> orderPrice) {

// define priority queues for buys and sells
priority_queue<pair<int, int>> buyQueue; // pairs of (price, quantity)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> sellQueue; // pairs of (price, quantity)

// add orders to the appropriate queue
for (int i = 0; i < numOrders; i++) {
    if (orderType[i] == 0) { // buy order
        buyQueue.push(make_pair(orderPrice[i], orderQuantity[i]));
    }
    else { // sell order
        sellQueue.push(make_pair(orderPrice[i], orderQuantity[i]));
    }
}

// iterate through the queues and match orders
int completedOrders = 0;
while (!buyQueue.empty() && !sellQueue.empty()) {
    pair<int, int> buyOrder = buyQueue.top();
    pair<int, int> sellOrder = sellQueue.top();
    if (buyOrder.first >= sellOrder.first) { // match found
        int minQuantity = min(buyOrder.second, sellOrder.second);
        completedOrders += minQuantity;
        buyQueue.top().second -= minQuantity;
        sellQueue.top().second -= minQuantity;
        if (buyQueue.top().second == 0) {
            buyQueue.pop();
        }
        if (sellQueue.top().second == 0) {
            sellQueue.pop();
        }
    }
    else { // no match found
        break;
    }
}

return completedOrders;

}

The time complexity of this solution is O(n log n) due to the use of priority queues. The space complexity is also O(n) because we need to store all the orders in the queues.

1