935. What Is Left in the Order Book

An exchange processes n orders in the given order. Each order has a price, an amount, and a type: 0 for a BUY, 1 for a SELL.

``` a BUY at price p: while it still has amount left and the book holds a SELL priced at or below p, match against the CHEAPEST such sell, reducing both amounts. Whatever remains of the buy joins the book.

a SELL at price p: while it still has amount left and the book holds a BUY priced at or above p, match against the DEAREST such buy. Whatever remains joins the book. ```

Print the total amount still sitting in the book after all n orders.

``` (10, 5, buy) (15, 2, sell) (25, 1, sell) (30, 4, buy) -> 6 the two sells at 15 and 25 rest in the book; the buy at 30 then takes both of them, 3 units in all, and its remaining 1 joins the book with the 5 from the first buy, giving 6

(7, 3, buy) -> 3 (5, 4, buy) (5, 4, sell) -> 0 ```

## What most people try first

Keeping the book as two plain lists and scanning for the best match each time is O(n) per order, so O(n^2). At n = 10^5 that is 10^10.

Keeping one sorted structure for everything does not work either, because the two sides are consulted from OPPOSITE ends: a buy wants the smallest sell, a sell wants the largest buy.

## The method: two heaps facing each other

buys a MAX-heap of (price, amount) sells a MIN-heap of (price, amount)

This is the second place in this block where two heaps are held in balance and neither is tracking a median. Problem #870 splits ONE set into two halves so the boundary is the answer. Here the two heaps hold two genuinely different things, and what matters is that each is oriented towards the other: the top of buys and the top of sells are the two orders most likely to trade.

for each order (p, a, type): if type is buy: while a > 0 and sells is non-empty and top(sells).price <= p: take = min(a, top(sells).amount) a = a - take; reduce the top's amount by take if the top is exhausted, pop it, otherwise stop reducing if a > 0: push (p, a) onto buys else symmetrically print the total amount left in both heaps

## Why one comparison per side is enough

The book might hold thousands of sells below p, and the loop only ever looks at the top of the heap. That is correct because the cheapest sell is matched first: if the top of sells is above p, every other sell is too, so the loop stops. If it is at or below p, it is the one the rule names.

Each iteration either exhausts a heap entry, which can happen at most once per entry over the whole run, or exhausts the incoming order, which ends the loop. So the total number of iterations across all n orders is at most 2n.

## The boundary that breaks a careless implementation

The match condition is sell price <= buy price, inclusive on both sides. Equal prices trade, which the third example checks; writing < leaves both orders resting in the book and the answer becomes 8 instead of 0.

A partially matched top must be pushed back or left in place with its amount reduced, not dropped. Popping it and forgetting the remainder silently deletes units from the book.

The incoming order joins the book only if something is LEFT of it. Pushing a zero-amount order leaves an entry that blocks the top of its heap and is never consumed.

## Overflow

Amounts reach 10^9 each and there are up to 10^5 orders, so the total left in the book reaches 10^14. The declared test with three buys of 10^9 at rising prices leaves 3 * 10^9, which a 32-bit accumulator reports as -1294967296. The running total needs 64 bits. Individual prices and amounts fit in 32 bits, and no product is ever formed.

## Related problems

Problem #870 is the other two-heap problem here and is the one everybody learns first. Problem #911 holds a free pool and a busy pool keyed by different things, which is closer to this shape: two heaps, two different questions, and the answer coming from the interaction rather than the boundary between them.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ price ≤ 10^9` - `1 ≤ amount ≤ 10^9` - The type is `0` or `1`.