A repair shop's help desk hands out service in order of urgency, not arrival. The day's log is a list of events:
("arrive", name, urgency): a customer callednamejoins the waiting area with an integer urgency (bigger means more urgent).("serve",): the clerk calls the waiting customer with the highest urgency. If several share that urgency, the one who arrived first goes. If nobody is waiting, the clerk calls nobody and the event is skipped.
Write serve_order(events: list[tuple]) -> list[str] that returns the names in the order they were served. Customers still waiting at the end of the day are not included.
serve_order([
("arrive", "ana", 2),
("arrive", "bo", 5),
("arrive", "cy", 5),
("serve",), # bo (urgency 5, arrived before cy)
("arrive", "di", 9),
("serve",), # di
("serve",), # cy
("serve",), # ana
("serve",), # nobody waiting: skipped
])
# ["bo", "di", "cy", "ana"]
- Up to 200,000 events. Urgencies may be negative. Names may repeat (two different customers can share a name), so don't use the name to break ties.
- Scanning the waiting area for the most urgent customer on every
serveis O(n) per event and too slow for the big test. Useheapq, so each event costs O(log n).
Show hint
heapq is a min-heap, so push (-urgency, arrival_number, name): the negation puts the most urgent on top, and an increasing arrival counter breaks ties by arrival (and stops Python from ever comparing names).