Job Scheduler with Delays and Cancellation

FigmaOnsiteMedium

A scheduler runs jobs on a fixed pool of workers identical workers. Time is an integer clock passed as now with every call, and it never decreases. Each worker runs one job at a time and a job runs without interruption: a job that starts at time s with duration d is running at times s through s + d - 1 and done from s + d onward. A free worker immediately takes the next waiting job, and a worker that finishes at time t can start another job at t.

Part 1: Immediate jobs

Implement submit(now, job_id, duration), which submits a job that should run as soon as possible. Jobs start in the order they were submitted, and submit returns nothing.

Implement status(now, job_id), which returns "queued" while the job waits for a worker, "running", "done", or None if no job with that id was submitted.

Example 1

init: [2]
operations: [["submit",[0,"a",5]],["submit",[0,"b",3]],["submit",[1,"c",2]],["status",[1,"a"]],["status",[1,"c"]],["status",[3,"b"]],["status",[3,"c"]],["status",[5,"a"]],["status",[5,"c"]],["status",[5,"zzz"]]]
Output: [null,null,null,"running","queued","done","running","done","done",null]

Why: Jobs a and b start at time 0 on the two workers; c arrives at 1 and queues. b finishes at 3, so c starts at 3 and finishes at 5, and a finishes at 5. An id that was never submitted has status None.

Constraints

1 <= workers <= 100
1 <= len(operations) <= 10^4
0 <= now <= 10^9, and now never decreases between calls
1 <= duration <= 10^9
1 <= len(job_id) <= 10
'a' <= job_id[i] <= 'z'
job_id values are pairwise distinct