Show problems as
Classic problem #1801MediumArrayHeap (Priority Queue)Simulation

Number of Orders in the Backlog

Real-world version: Lots Left on the Produce Book
Tracked in this browser only
Read Number of Orders in the Backlog on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A produce desk works through instructions in the order logged. Each entry of orders is [price, lots, kind], where kind is 0 for a buy and 1 for a sell.

A buy is filled lot by lot against the cheapest sell waiting on the book, so long as that sell's price is at most the buy's price. A sell is filled against the dearest buy waiting, so long as that buy's price is at least the sell's price. Filling removes lots from both sides, and a waiting order leaves the book once all its lots are gone. Whatever cannot be filled joins the book itself.

Return the total lots left on the book once every instruction has been worked through, modulo 10^9 + 7.

Examples

Example 1

Input
orders = [[23, 5, 0], [19, 4, 1], [26, 3, 1], [21, 7, 0]]
Output
11

The buy at 23 goes on the book first. The sell at 19 fills 4 of its lots, leaving 1 buy lot at 23. The sell at 26 finds no buy dear enough and joins the book. The buy at 21 finds the cheapest sell priced 26, which is too dear, so its 7 lots join too, leaving 1 plus 3 plus 7 lots waiting.

Example 2

Input
orders = [[10, 5, 0], [11, 5, 1]]
Output
10

The sell wants 11 a lot and the only buy offers 10, so nothing fills and all ten lots stay on the book.

Example 3

Input
orders = [[10, 5, 0], [10, 5, 1]]
Output
0

An equal price is good enough to fill, so the two orders clear each other out.

Constraints

  • 1 <= orders.length <= 10^5
  • orders[i].length == 3
  • 1 <= orders[i][0] <= 10^9
  • 1 <= orders[i][1] <= 10^9
  • orders[i][2] is either 0 or 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def get_number_of_backlog_orders(orders: list[list[int]]) -> int:
Java
public int getNumberOfBacklogOrders(int[][] orders)

More on the same topics