A small exchange trades one coin. At the opening bell it has two books of limit orders, each for exactly one coin:
sells[j]is the lowest price thej-th seller will accept;buys[i]is the highest price thei-th buyer will pay.
The engine then walks through the buy orders in the order given. For buy i:
- among the sell orders that are still open and priced
<= buys[i], it picks the cheapest one (the buyer pays as little as possible), and the two orders fill at that sell's price; the sell order is used up; - if no open sell is priced
<= buys[i], buyigoes unfilled.
A buy never waits for a later sell; each buy is decided when the engine reaches it.
Write match_orders(buys: list[int], sells: list[int]) -> tuple[list[int], list[int]] that returns:
fills: for each buy in order, the price it paid, or-1if it went unfilled;left: the prices of the sell orders nobody filled, sorted ascending.
match_orders(buys=[100, 90, 120, 95], sells=[105, 92, 98, 130])
# fills: [92, -1, 98, -1]
# buy 100 -> cheapest sell is 92, fills at 92
# buy 90 -> cheapest open sell is 98 > 90, unfilled
# buy 120 -> fills at 98
# buy 95 -> cheapest open sell is 105 > 95, unfilled
# left: [105, 130]
Constraints: up to 200,000 orders on each side; prices are integers in 1..10**9; either list may be empty; prices may repeat.
Show hint
Only the cheapest open sell ever matters. Which data structure hands you the minimum and lets you remove it in O(log n)?