The title
1801. Total number of orders in backlog
Orderorders [I] = [pricei, amounti, orderTypei] = [pricei, amounti, orderTypei]
OrderTypei can be divided into two types:
- 0 indicates that this is a batch of purchase orders buy
- 1 indicates that this is a batch of sales orders
Note that orders[I] represents a number of separate orders totaling amounti pens at the same price and type. For all valid I, all orders represented by Orders [I] are submitted earlier than all orders represented by Orders [I +1].
There is a backlog of unexecuted orders. The backlog was initially empty. When you submit an order, the following happens:
If the order is a purchase order Buy, you can view the sale order Sell with the lowest price in the backlog. If the price of the sales order Sell is less than or equal to the price of the current purchase order Buy, the two orders are matched and executed, and the sales order Sell is removed from the backlog. Otherwise, the purchase order Buy will be added to the backlog. Vice versa, if the order is a sell order, you can view the purchase order buy with the highest price in the backlog. If the price of the purchase order Buy is higher than or equal to the price of the current sales order Sell, the two orders are matched and executed, and the purchase order Buy is removed from the backlog. Otherwise, the sales order Sell will be added to the backlog. After entering all orders, the total number of orders in the backlog is returned. Since the numbers can be large, you need to return mod 109 + 7.
Example 1:
Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]] output: 6 explanation: after entering the order, the following occurs: - submit 5 purchase orders for a price of 10. There are no sales orders, so these 5 orders are added to the backlog. - Submit 2 sales orders at a price of 15. No purchase order has a price greater than or equal to 15, so these 2 orders are added to the backlog. - Submit a sales order at a price of 25. No purchase order has a price greater than or equal to 25, so this 1 order is added to the backlog. - Submit 4 purchase orders for 30. The first two purchase orders match the two sales orders with the lowest price (price 15) and are deleted from the backlog. The third purchase order matches the lowest sales order with a price of 25, which is removed from the backlog. There are no more sales orders in the backlog, so a fourth purchase order needs to be added to the backlog. Finally, there are five purchase orders at 10 and one purchase order at 30 in the backlog. So the total number of orders in the backlog is 6.Copy the codeExample 2:
Input: orders = [[7,1000000000,1],[15,3,0],[5,99999995,0],[5,1,1]] output: 999999984 explanation: after entering an order, the following occurs: - 109 sales orders are submitted at price 7. There are no purchase orders, so the 109 orders are added to the backlog. - Submit 3 purchase orders at a price of 15. These purchase orders are matched with the three sales orders with the lowest price (price 7), which are removed from the backlog. - Submit 999999995 purchase orders at price of 5. The minimum price of the sales order is 7, so 99,99,995 orders are added to the backlog. - Submit a sales order at a price of 5. This sales order matches the purchase order with the highest price (price 5), which is deleted from the backlog. Finally, there are (1000000,000-3) sales orders at 7 and (999999995-1) purchase orders at 5 in the backlog. So the total number of orders in the backlog is 199,999,999,991, which is 999,999,984% (109 + 7).Copy the code
Ideas:
To close an order, we need to split it to meet the following two points
- Both the buy and sell orders are greater than 0
- The purchase price is greater than the sale price
There are three things that can happen in an order transaction
- If the number of purchases is greater than the number of sales, the sold orders can be eaten up, leaving purchase orders to be processed
- If the purchase quantity equals the sold quantity, the purchase order will be eaten up and the sold order will be left
- The quantity bought is equal to the quantity sold, so both are cleared
In combination with this question, each order processed may be a purchase order or a sale order, so let’s analyze the logic completely based on the above logic
- Define two empty priority queues sorted by price, one is BuyQ, which has the highest price of the queue head element, and the other is SellQ, which has the lowest price of the queue head element.
- Iterate through the entire array of pending orders, order processing in sequence
- If it is a purchase order, it judges whether the current SellQ is empty; if it is not empty, it judges whether the current order price is greater than the price of the head element of the SellQ queue; if it is larger, it concludes a transaction. Less than the current order into BuyQ
- When the transaction is available, determine the relationship between the current order quantity and the SellQ quantity and put them in their priority queue as analyzed above, that is, who is left or who is left
- After processing, count the remaining elements of both queues to get the total number of backlogs
This problem we use JS to do, need to implement a binary heap based priority queue, the following code has detailed logic
There is a point here that I have been struggling with for a long time, which is when the priority queue sinks, what if two children have the same value?
In fact, in this case, the node can go either way, which is the logic of the priority queue, you don’t have to worry about it
The whole topic code implementation is as follows:
/ * * *@param {number[][]} orders
* @return {number}* /
var getNumberOfBacklogOrders = function(orders) {
// The priority queue class is not directly distinguished between the big top heap and the small top heap
let cmp = function(a, b){
return a[0] < b[0]};let BuyQ = new Heap(cmp); / / big heap
let SellQ = new Heap(); / / small cap pile
orders.forEach((order) = >{
if (order[2] = =0) { // The current order is Buy, we need to find the smallest Sell
while (order[1] > 0 && !SellQ.isEmpty() && order[0] >= SellQ.peek()[0]) {// If the current order number is greater than 0, the current order price >= Sell minimum
if (order[1] > SellQ.peek()[1]) { // Current order number > current order number
order[1] -= SellQ.poll()[1]; // The lowest price in Sell was removed
} else if (order[1] == SellQ.peek()[1]) { // Current order number == lowest order number
// The lowest price in Sell was removed
SellQ.poll();
order[1] = 0;
} else if (order[1] < SellQ.peek()[1]) { // Current order number < Sell minimum order number
// Update the order quantity of the Sell lowest price
SellQ.heap[0] [1] = SellQ.heap[0] [1]-order[1]
order[1] = 0; }}if (order[1] > 0) {// If the current order remains, the order will be queued
let buyOrder = [order[0], order[1]] BuyQ.offer(buyOrder); }}else {
// The current order is Sell, we need to find the largest Buy
while (order[1] > 0 && !BuyQ.isEmpty() && BuyQ.peek()[0] >= order[0]) { // If the current order number is greater than 0, Buy Max price >= current order price
if (order[1] > BuyQ.peek()[1]) { // Current order number > Buy
order[1] -= BuyQ.poll()[1]; //Buy is deleted
} else if (order[1] == BuyQ.peek()[1]) { // Current order == Buy highest order
BuyQ.poll(); //Buy is deleted
order[1] = 0;
} else if (order[1] < BuyQ.peek()[1]) { // Current order number < Buy the highest order number
BuyQ.heap[0] [1] = BuyQ.heap[0] [1]- order[1];
order[1] = 0; }}if (order[1] > 0) {// If the current order remains, the order will be queued
let sellOrder = [order[0], order[1]] SellQ.offer(sellOrder); }}})let count = 0;
// The backlog is the backlog of each node of the two heaps
for (let arr of BuyQ.heap) {
count += arr[1];
}
for (let arr of SellQ.heap) {
count += arr[1];
}
return count % 1000000007;
};
// Default small top heap
var defaultCmp = function(a, b){
return a[0] > b[0]};class Heap {
constructor(cmp=defaultCmp) {
this.heap = []; // Each node structure is [price, amount]
this.cmp = cmp;
}
isEmpty(){
return !this.heap.length > 0
}
peek(){
return this.heap[0]}offer(node){
this.heap.push(node)
this.siftUp(this.heap.length-1);
}
poll(){
// First fetch the queue head node
let node = this.heap[0];
// Assign the last node to the head node
this.heap[0] = this.heap[this.heap.length-1]
// Delete the last node
this.heap.pop();
// Reorder from top to bottom
this.siftDown(0);
return node;
}
siftUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) /2)
// Compare the value of the current element with the parent element based on the current size of the top heap to determine whether to swap
if (this.cmp(this.heap[parent], this.heap[i])) {
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
} else {
break; }}}siftDown(i) {
while (2 * i + 1 < this.heap.length) {// Determine whether there are child nodes
let child = 2 * i + 1;
// If the child node has sibling elements, determine who should be compared to the current node based on the size of the top heap
if (child + 1 < this.heap.length && this.cmp(this.heap[child], this.heap[child + 1])) {
child++;
}
// Compare the current node with its children to see if it wants to swap
if (this.cmp(this.heap[i], this.heap[child])) {
[this.heap[child], this.heap[i]] = [this.heap[i], this.heap[child]];
i = child;
} else {
break; }}}}Copy the code