When a worker claims a task, it gets a lease that runs out at a deadline. If the worker doesn't finish (or renew) in time, the queue must notice and hand the task to someone else. This drill is just that bookkeeping.
Build Leases with:
grant(task_id, deadline) -> None: the task is leased untildeadline(an int). Granting a task that already has a lease replaces its deadline (this is how a heartbeat extends a lease, and a deadline can move earlier too).release(task_id) -> None: the worker finished; the task no longer has a lease. Releasing an unknown task does nothing.expired(now) -> list[str]: remove and return every leased task whose deadline is<= now, ordered by deadline, ties broken by task id. A returned task no longer has a lease.
L = Leases()
L.grant("a", 10)
L.grant("b", 5)
L.grant("c", 5)
L.grant("a", 20) # heartbeat: a now expires at 20
L.release("c") # c is done
L.expired(9) # ["b"]
L.expired(9) # [] (b was already returned)
L.expired(25) # ["a"]
Many tasks can be leased at once, so expired must not look at every leased task on each call.
Show hint
push (deadline, task_id) onto a heapq and keep a dict of each task's current deadline; when you pop an entry that doesn't match the dict (released or re-granted), skip it (lazy deletion).