Implement a Time-Aware Task Manager

Problem Statement

Design and implement an in-memory time-aware task management system. The system maintains tasks on a per-user basis where each task version is associated with a creation timestamp and a time-to-live (ttl). A task is considered active at timestamp t if it was set at start_time and start_time <= t < start_time + ttl, provided it has not been overwritten or deleted before t.

All mutation calls (set_task and delete_task) arrive in non-decreasing order of timestamp across the entire system. Queries (get_task_at and get_active_tasks_at) may specify any arbitrary non-negative timestamp (past, present, or future relative to mutations seen so far).

Implement the TimeAwareTaskManager class:

• __init__(): Initializes the data structures.
• set_task(user_id: str, task_id: str, payload: str, timestamp: int, ttl: int) -> None: Creates or updates a task for user_id. The task becomes active at timestamp and expires at timestamp + ttl. If a prior version of this task was still active at timestamp, its validity ends at timestamp.
• delete_task(user_id: str, task_id: str, timestamp: int) -> bool: Deletes task_id for user_id starting at timestamp. Returns True if the task was currently active at timestamp (and is now terminated), or False if the task was already expired, deleted, or never existed.
• get_task_at(user_id: str, task_id: str, timestamp: int) -> str | None: Returns the payload of task_id for user_id at timestamp. Returns None if the task was not active at that timestamp.
• get_active_tasks_at(user_id: str, timestamp: int) -> list[str]: Returns a list of all active task_ids for user_id at timestamp, sorted lexicographically.

Constraints

• 1 <= len(user_id), len(task_id), len(payload) <= 32
• 0 <= timestamp <= 10^9
• 1 <= ttl <= 10^6
• Timestamps for mutation operations (set_task, delete_task) are non-decreasing: timestamp_k <= timestamp_{k+1}.
• At most 5 * 10^4 total calls across all methods.
• At most 200 unique task_ids per user.

Example

tm = TimeAwareTaskManager()

# User 'alice' creates task 'T1' at t=10 with TTL=15 (valid in [10, 25))
tm.set_task("alice", "T1", "Payload A", 10, 15)

# User 'alice' updates task 'T1' at t=20 with TTL=10 (valid in [20, 30))
# Prior version now only valid in [10, 20)
tm.set_task("alice", "T1", "Payload B", 20, 10)

# User 'alice' creates task 'T2' at t=22 with TTL=5 (valid in [22, 27))
tm.set_task("alice", "T2", "Payload C", 22, 5)

assert tm.get_task_at("alice", "T1", 15) == "Payload A"
assert tm.get_task_at("alice", "T1", 20) == "Payload B"
assert tm.get_task_at("alice", "T1", 25) == "Payload B"
assert tm.get_task_at("alice", "T1", 30) is None  # Expired at t=30

assert tm.get_active_tasks_at("alice", 24) == ["T1", "T2"]
assert tm.get_active_tasks_at("alice", 28) == ["T1"]

# Delete T1 at t=29 (returns True because T1 is active at t=29)
assert tm.delete_task("alice", "T1", 29) is True
assert tm.get_task_at("alice", "T1", 29) is None
assert tm.delete_task("alice", "T1", 35) is False  # Already expired/deleted

Edge Cases

• Overwriting a task before its previous TTL has expired should curtail the prior version's end time to the new mutation's timestamp.
• Deleting an already expired task returns False and does not extend or revive any state.
• timestamp exactly at expiration time t = start_time + ttl must be considered expired.