Matching Engine Price Time
MediumTrading · IMC
Implement a simple matching engine. Orders arrive one at a time in the order given; each is [order_id, side, limit_price, quantity], where side is "B" (buy) or "S" (sell).
When an order arrives, it trades against resting orders on the opposite side for as long as it has quantity left and the best resting order is compatible:
- An incoming buy is compatible with a resting sell whose price is
<=the buy's limit. The best resting sell is the one with the lowest price; among equal prices, the one that arrived earliest. - An incoming sell is compatible with a resting buy whose price is
>=the sell's limit. The best resting buy is the one with the highest price; among equal prices, the one that arrived earliest.
Each trade is for min(incoming remaining, resting remaining) units at the resting order's price. A resting order that reaches 0 leaves the book. If the incoming order still has quantity left when no compatible order remains, the rest of it is added to the book with its own arrival time; a partially filled resting order keeps its original priority.
Return every trade as [buy_order_id, sell_order_id, price, quantity] in the order the trades happen.
Example 1
- Input:
- orders = [["s1", "S", 101, 4], ["s2", "S", 100, 3], ["s3", "S", 100, 5], ["b1", "B", 101, 10]]
- Output:
- [["b1", "s2", 100, 3], ["b1", "s3", 100, 5], ["b1", "s1", 101, 2]]
- Explanation
- When
b1arrives, the best ask is 100, wheres2arrived befores3, sob1buys 3 froms2and then 5 froms3, both at 100. Its remaining 2 trade withs1at 101. Each trade uses the resting order's price.
Example 2
- Input:
- orders = [["b1", "B", 50, 5], ["b2", "B", 52, 2], ["s1", "S", 51, 4]]
- Output:
- [["b2", "s1", 52, 2]]
- Explanation
- The best bid is
b2at 52, sos1sells 2 there. The next bid,b1at 50, is belows1's limit of 51, so the remaining 2 units ofs1rest on the book and no further trade happens.
Example 3
- Input:
- orders = [["s1", "S", 9, 3], ["b1", "B", 10, 5], ["s2", "S", 10, 4]]
- Output:
- [["b1", "s1", 9, 3], ["b1", "s2", 10, 2]]
- Explanation
b1buys 3 froms1at 9 and rests with 2 left at 10. Whens2arrives at 10 it crossesb1, and they trade 2 at 10, the resting buy's price.
Constraints
1 <= orders.length <= 10^51 <= limit_price <= 10^9,1 <= quantity <= 10^6- Order ids are unique strings;
sideis"B"or"S"