A help desk serves the most urgent ticket first. Write serve(events: list[tuple]) -> list[str | None] that processes events in order:
("add", name, priority):namefiles a ticket with an integerpriority. A smaller number is more urgent (1 beats 2).("next",): serve one ticket: the most urgent waiting ticket, and among equally urgent tickets the one added first. Append itsnameto the result, orNoneif no ticket is waiting.
Return the result list.
serve([("add", "zed", 2), ("add", "amy", 2), ("add", "bob", 1),
("next",), ("next",),
("add", "cat", 1),
("next",), ("next",), ("next",)])
# ["bob", "zed", "cat", "amy", None]
zed is served before amy: same priority, and zed's ticket came first, even though "amy" < "zed".
0 <= len(events) <= 2 * 10^5; priorities are in[1, 10^9]; names are lower-case letters, and one person can file several tickets.
⭐ Bonus: scanning all waiting tickets on every "next" is O(n²) and still passes; a speed test with 200,000 events earns a star at O(log n) per event.
Show hint
heapq with tuples. Tuples compare item by item, so put the priority first, then something that breaks ties by arrival, then the name.