Orders arrive one at a time. Each order is a pair [side, price], where side is 1 for a buy and -1 for a sell, and price is a positive integer. Every order is for exactly one share.
When an order arrives:
- Buy at price
p: if any resting sell has price<= p, it trades against the cheapest such sell. The trade happens at the resting sell's price, and both orders leave the book. Otherwise the buy rests in the book. - Sell at price
p: if any resting buy has price>= p, it trades against the highest such buy, at the resting buy's price. Both orders leave the book. Otherwise the sell rests.
Each order trades at most once. Write
def total_traded_value(orders: list[list[int]]) -> int
returning the sum of the prices of all trades.
total_traded_value([[1, 10], [-1, 12], [-1, 9], [1, 13]])
# buy 10 rests; sell 12 rests (10 < 12);
# sell 9 hits the buy at 10 -> trade at 10;
# buy 13 hits the sell at 12 -> trade at 12
# -> 22
Constraints: up to 2 * 10**5 orders; 1 <= price <= 10**9. A linear scan of the book for every order is too slow: aim for O(log n) per order.
Show hint
Each arriving order only ever cares about the single best resting order on the opposite side. Keep each side in a structure that gives you its best price and removes it quickly.