Fault-tolerant work queue with leases and retries

Implement an in-memory work queue that keeps working when workers crash. Workers take a task, process it, and report success or failure. A worker that dies silently must not lose the task: every reservation is a lease that runs out.

class WorkQueue:
    def __init__(self, lease_seconds: int, max_attempts: int): ...
    def add(self, task_id: str, now: int) -> bool: ...
    def reserve(self, now: int) -> str | None: ...
    def complete(self, task_id: str, now: int) -> bool: ...
    def fail(self, task_id: str, now: int) -> str | None: ...
    def status(self, task_id: str, now: int) -> str | None: ...

Every call passes the current time now. Times never go down between calls.

Rules

• A task is in one of four states: AVAILABLE, RESERVED, COMPLETED, DEAD.
• add puts a new task at the back of the available line and returns True. Adding an id that already exists returns False and changes nothing.
• reserve takes the task at the front of the available line, marks it RESERVED, counts one attempt, and returns its id. The lease ends at now + lease_seconds. Return None if no task is available.
• complete succeeds (returns True) only if the task is currently RESERVED; it becomes COMPLETED. Otherwise return False.
• fail works only on a RESERVED task (otherwise return None). If the task has used fewer than max_attempts attempts, it goes to the back of the available line and fail returns "AVAILABLE". If it has used all of them, it becomes DEAD and fail returns "DEAD".
• Lease expiry: before handling any call at time now, every lease whose end time is <= now expires. An expired lease is handled exactly like fail (retry or dead-letter). Leases that end at the same time expire in the order they were reserved.
• status returns the task's state, or None for an unknown id.

Aim for O(log n) or better per call. Talk through how you find expired leases without scanning every task.

Constraints: up to 2 * 10^5 calls; times up to 10^9; 1 <= max_attempts <= 10^5; 0 <= lease_seconds <= 10^9.

Example 1

q = WorkQueue(lease_seconds=30, max_attempts=3)
q.add("resize-7", 0)    -> True
q.add("resize-8", 0)    -> True
q.reserve(5)            -> "resize-7"
q.fail("resize-7", 9)   -> "AVAILABLE"   # retried, now behind resize-8
q.reserve(10)           -> "resize-8"
q.reserve(11)           -> "resize-7"
q.complete("resize-8", 20) -> True

Example 2

q = WorkQueue(lease_seconds=4, max_attempts=2)
q.add("emb-1", 0)       -> True
q.reserve(1)            -> "emb-1"       # lease ends at 5
q.status("emb-1", 5)    -> "AVAILABLE"   # the worker went silent
q.reserve(6)            -> "emb-1"       # second attempt, ends at 10
q.complete("emb-1", 11) -> False         # too late: the lease expired at 10
q.status("emb-1", 11)   -> "DEAD"