Job Scheduler

Design a scheduler that runs functions. A caller can ask to run a job after a delay, at an absolute time, or repeatedly on a fixed interval. A single background worker thread fires each job as close to its due time as possible.

Implement the JobScheduler class:

• JobScheduler() Initializes the scheduler and starts one background worker thread.
• int schedule(fn, delay) Schedules fn to run once, delay seconds from now. Returns a unique job id.
• int schedule_at(fn, timestamp) Schedules fn to run once at the absolute time timestamp. Returns a unique job id.
• int schedule_every(fn, interval) Schedules fn to run repeatedly, every interval seconds, starting interval seconds from now. Returns a unique job id.
• void cancel(job_id) Cancels the job with id job_id. The job never runs again.

The scheduler must satisfy all of the following:

• Jobs fire in due-time order, regardless of the order they were added.
• Adding a job that is due sooner than everything queued wakes the worker early — no fixed polling interval.
• The worker waits while idle; it does not busy-spin.
• cancel reliably prevents all future runs of a job.
• All access to shared state is synchronized.

Example 1:

Input
["JobScheduler", "schedule", "schedule"]
[[], [fnA, 10], [fnB, 1]]
Output
[null, 1, 2]

Explanation
JobScheduler s = new JobScheduler();
s.schedule(fnA, 10);   // return 1; fnA is due at t = 10
s.schedule(fnB, 1);    // return 2; fnB is due at t = 1

fnB fires at t = 1 even though it was added second. The worker was sleeping
until t = 10 and must wake early when the sooner job arrives. fnA fires at
t = 10.

Example 2:

Input
["JobScheduler", "schedule", "cancel"]
[[], [cleanup, 60], [1]]
Output
[null, 1, null]

Explanation
JobScheduler s = new JobScheduler();
s.schedule(cleanup, 60);   // return 1; cleanup is due at t = 60
s.cancel(1);               // cleanup never runs

Example 3:

Input
["JobScheduler", "schedule_every", "cancel"]
[[], [heartbeat, 1], [1]]
Output
[null, 1, null]

Explanation
JobScheduler s = new JobScheduler();
s.schedule_every(heartbeat, 1);   // return 1; fires at t = 1, 2, 3, ...
...                               // heartbeat fires once per second
s.cancel(1);                      // after this, heartbeat never fires again

Constraints:

• 1 <= delay, interval <= 10^4
• timestamp is a valid future time.
• At most 10^4 calls will be made to schedule, schedule_at, schedule_every, and cancel combined.
• Job functions run quickly; assume their runtime is negligible.

Starter code:

class JobScheduler:
    def __init__(self):
        ...

    def schedule(self, fn, delay):
        ...

    def schedule_at(self, fn, timestamp):
        ...

    def schedule_every(self, fn, interval):
        ...

    def cancel(self, job_id):
        ...

Follow-ups

• If the process restarts, how would you make the schedule survive so jobs aren't lost?

• And more...