Task processor with dependencies and deadlines

medium 3 levels ~60 min Scale AI

Level 1 Earliest deadline first

Build a TaskProcessor that hands out work in deadline order.

add_tasks(tasks) -> None: tasks is a list of dicts like {"id": "a7", "deadline": 12}. Ids are strings and unique across all calls; deadlines are integers (possibly negative or repeated). Tasks can be added at any time, including between consumes.
consume_task() -> str | None: remove the unconsumed task with the smallest deadline and return its id. Break deadline ties by the smaller id (plain string comparison). Return None when nothing is left.

Both operations should be O(log n) per task.

p = TaskProcessor()
p.add_tasks([{"id": "x", "deadline": 5}, {"id": "b", "deadline": 3}, {"id": "a", "deadline": 5}])
p.consume_task()   # "b"
p.consume_task()   # "a"   (tie on 5, "a" < "x")
p.add_tasks([{"id": "q", "deadline": 1}])
p.consume_task()   # "q"
p.consume_task()   # "x"
p.consume_task()   # None

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Heap scheduling (deadlines, leases). Min-heap of deadlines, lazy deletion, event simulation.

Read the visual guide