progress

~/problems / Arrays & hashing / Python toolkit

Help desk queue with heapq

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

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): name files a ticket with an integer priority. 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 its name to the result, or None if 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.

Topic: Python toolkit. Counter, deque, heapq, bisect, itertools: the standard library to know cold, and its traps.

0:00
Ctrl ' run · Ctrl ↵ submit
esc