OA: Marketplace trading system with order matching

You're building the matching core of an online marketplace. Sellers list items for sale at a price; buyers ask to buy an item and name the most they will pay. One item can have many listings, each from a different seller and at its own price.

class TradingSystem:
    def __init__(self): ...
    def list_item(self, seller: str, item: str, price: int) -> int: ...
    def buy(self, buyer: str, item: str, max_price: int) -> int | None: ...
    def cancel(self, order_id: int) -> bool: ...
    def best_price(self, item: str) -> int | None: ...

• list_item puts one unit of item up for sale and returns a new order id. Ids are 1, 2, 3, ... in call order.
• buy purchases one unit of item from the cheapest active listing priced <= max_price. If several listings share that price, the one listed earliest (lowest id) wins. The listing is used up. Return its id, or None if nothing qualifies (the buyer then simply goes away).
• A buyer never buys from their own listings: skip them (they stay on sale) and consider the next best.
• cancel withdraws an active listing and returns True. It returns False for an unknown id or a listing that was already sold or cancelled.
• best_price is the cheapest active listing price for item, or None.

Prices are integers in 1..10**6. Item and user names are arbitrary strings.

ts = TradingSystem()
ts.list_item("ann", "lamp", 30)   # 1
ts.list_item("bob", "lamp", 25)   # 2
ts.list_item("cat", "lamp", 25)   # 3
ts.buy("dan", "lamp", 20)         # None: nothing that cheap
ts.buy("dan", "lamp", 40)         # 2: cheapest is 25; bob listed before cat
ts.cancel(3)                      # True
ts.cancel(3)                      # False
ts.best_price("lamp")             # 30
ts.buy("ann", "lamp", 100)        # None: the only listing left is ann's own

Constraints: up to 200,000 calls, concentrated on a few popular items. Scanning every listing on each buy is too slow: list_item, buy, cancel and best_price should each cost about O(log n) amortised.