Build a Removable Timestamp-Ordered Task Scheduler

Problem Statement

Design a task scheduler that manages tasks scheduled to run at specific timestamps. Each task has a unique integer task_id and an execution timestamp.

Implement the TaskScheduler class:

• TaskScheduler(): Initializes an empty scheduler.
• add_task(task_id: int, timestamp: int) -> None: Adds a task with the given task_id and timestamp. If task_id already exists in the scheduler, update its scheduled timestamp to the new value.
• remove_task(task_id: int) -> bool: Cancels and removes the task with task_id. Returns True if the task existed and was removed, or False if it was not found.
• pop_ready_tasks(current_time: int, max_count: int) -> list[int]: Retrieves and removes up to max_count tasks whose timestamp <= current_time. Tasks must be returned in ascending order of their timestamp. If multiple tasks have the exact same timestamp, ties must be broken by smaller task_id first.

Interface

class TaskScheduler:
    def __init__(self):
        pass

    def add_task(self, task_id: int, timestamp: int) -> None:
        pass

    def remove_task(self, task_id: int) -> bool:
        pass

    def pop_ready_tasks(self, current_time: int, max_count: int) -> list[int]:
        pass

Examples

Example 1

scheduler = TaskScheduler()
scheduler.add_task(101, 15)
scheduler.add_task(102, 10)
scheduler.add_task(103, 15)
scheduler.add_task(104, 20)

# Pop up to 2 tasks ready by time 15
# Tasks ready: 102 (time 10), 101 (time 15), 103 (time 15)
# Order: 102, then tie between 101 and 103 -> 101 has smaller ID
print(scheduler.pop_ready_tasks(15, 2))  # Output: [102, 101]

# Cancel task 104
print(scheduler.remove_task(104))        # Output: True
print(scheduler.remove_task(999))        # Output: False

# Reschedule task 103 to timestamp 25
scheduler.add_task(103, 25)

# Check ready tasks at time 20
print(scheduler.pop_ready_tasks(20, 5))  # Output: []

# Check ready tasks at time 30
print(scheduler.pop_ready_tasks(30, 5))  # Output: [103]

Constraints

• 1 <= task_id <= 10^9
• 0 <= timestamp, current_time <= 10^12
• 1 <= max_count <= 10^5
• At most 2 * 10^5 total calls will be made across all methods.

Edge Cases to Consider

• Calling pop_ready_tasks when no tasks have timestamp <= current_time.
• Overwriting an existing task with a newer or older timestamp.
• Removing a task and adding it again later.
• max_count larger than the total number of ready tasks.