Limit Order Book Matching Engine

Problem: Implement a Limit Order Book Matching Engine Implement a simplified exchange limit order book matching engine. The system receives N limit orders in sequence. Each order has the format: side order_id price quantity where: side is either BUY or SELL; order_id is a unique integer order identifier; price is a positive integer limit price; quantity is a positive integer quantity. Matching rules When an incoming order arrives, it first matches against eligible resting orders already in the book: A buy order can trade with sell orders priced <= its limit price. A sell order can trade with buy orders priced >= its limit price. Buy orders consume the lowest ask first; sell orders consume the highest bid first. At the same price, orders are matched in price-time priority (FIFO). The execution price is the price of the resting order. An order may be partially filled and may match multiple counterparties. Any unfilled portion of the incoming order becomes a resting order in the book. For every execution, print: TRADE buy_order_id sell_order_id execution_price execution_quantity If an order produces no trades, print nothing. No final order-book output is required. Input format N side order_id price quantity side order_id price quantity ... Output format Print all trades in execution order. Example Input: 4 BUY 1 100 10 SELL 2 105 5 SELL 3 99 6 BUY 4 110 3 Output: TRADE 1 3 100 6 TRADE 4 2 105 3 Constraints 1 <= N <= 200,000 1 <= order_id <= 10^9, and all IDs are unique 1 <= price, quantity <= 10^9 Aim for total time complexity close to O(N log N + T), where T is the number of executions. Example Input 4 BUY 1 100 10 SELL 2 105 5 SELL 3 99 6 BUY 4 110 3 Output TRADE 1 3 100 6 TRADE 4 2 105 3