Schedule Priority Jobs with Cooldowns

Problem Statement

Design a recurring job scheduler that supports adding recurring tasks and retrieving the next task to execute based on priority and cooldown constraints.

Implement the JobScheduler class:

• JobScheduler(): Initializes the scheduler.
• void add_job(str job_id, int priority, int cooldown): Registers a recurring job with a unique identifier job_id, an integer priority (larger values indicate higher priority), and a non-negative integer cooldown. If job_id already exists, update its priority and cooldown.
• str | None get_next_job(): Selects and returns the job_id of the highest-priority currently eligible job. If multiple eligible jobs have the same priority, select the one that was added or updated earliest (FIFO tie-breaking). If no jobs are eligible, returns None.

Cooldown Semantics

• Each call to get_next_job() represents one discrete time step (tick t = 1, 2, 3, ...), regardless of whether a job is returned or None is returned.
• When a job is returned at tick t with cooldown k, it enters cooldown and cannot be returned again until at least k subsequent calls to get_next_job() have completed. That is, it becomes eligible again at tick t + k + 1.
• A job with cooldown = 0 can be executed again on the very next call (t + 1).
• Once scheduled, jobs are recurring: they return to the pool of candidate jobs as soon as their cooldown expires.

Examples

Example 1

scheduler = JobScheduler()
scheduler.add_job("A", priority=10, cooldown=2)
scheduler.add_job("B", priority=5, cooldown=0)

# Call 1 (t=1): "A" (priority 10) is chosen. "A" is on cooldown until t = 1 + 2 + 1 = 4.
scheduler.get_next_job()  # Returns "A"

# Call 2 (t=2): "A" is cooling down. "B" is eligible.
scheduler.get_next_job()  # Returns "B"

# Call 3 (t=3): "A" is still cooling down. "B" (cooldown 0) is eligible.
scheduler.get_next_job()  # Returns "B"

# Call 4 (t=4): "A" cooldown has expired. "A" (priority 10) > "B" (priority 5).
scheduler.get_next_job()  # Returns "A"

Example 2

scheduler = JobScheduler()
scheduler.add_job("Task1", priority=5, cooldown=1)

scheduler.get_next_job()  # Call 1 (t=1): Returns "Task1"
scheduler.get_next_job()  # Call 2 (t=2): Returns None (Task1 eligible at t=3)
scheduler.get_next_job()  # Call 3 (t=3): Returns "Task1"

Constraints

• 1 <= len(job_id) <= 32
• 1 <= priority <= 10^9
• 0 <= cooldown <= 10^5
• At most 2 * 10^5 total calls to add_job and get_next_job.
• Memory usage should be proportional to the number of distinct jobs.