Named Async Task Scheduler
Airwallex● HardFULLTIMEOAProblem statement
Simulate an asynchronous task scheduler. Process operations in order while maintaining a virtual clock that starts at 0.
Operations
["ADD", name, taskId, duration]: add a task with a positive integer duration. If no task with that name is running, start it now; otherwise append it to that name's FIFO queue.["ADVANCE", delta]: advance the clock by a nonnegative integer delta and process every task completion at or before the target time.["CANCEL", name]: cancel the currently running task with that name. If one exists, immediately start the next queued task of the same name. It does not remove the remaining queue.["CLEAR", name]: remove the running task and every queued task with that name. It never affects another name.
Tasks with the same name never overlap. Tasks with different names may run concurrently.
Completion ordering
A queued task starts at the exact time its predecessor finishes or is cancelled. During ADVANCE, process completions by smaller finish time, then by lexicographically smaller task name. For each selected completion, record its FINISH event and start that name's next task before processing the next completion. Durations are positive, so a newly started task cannot finish at the same instant.
After processing completions, set the clock to the target time. A task finishing exactly at the target completes before the next input operation. Do not automatically drain unfinished work after the final operation.
Return value
Return every lifecycle event in order using these exact forms:
time:START:name:taskIdtime:QUEUE:name:taskIdtime:FINISH:name:taskIdtime:CANCEL:name:taskId, ortime:CANCEL_NONE:nametime:CLEAR:name:taskIdfor the running task first and then queued tasks in FIFO order, ortime:CLEAR_NONE:name
Function
runNamedTaskScheduler(operations: String[][]) → String[]Examples
Example 1
operations = [["ADD","alpha","a1","5"],["ADD","alpha","a2","2"],["ADD","beta","b1","3"],["ADVANCE","3"],["ADVANCE","2"],["ADVANCE","2"]]return = ["0:START:alpha:a1","0:QUEUE:alpha:a2","0:START:beta:b1","3:FINISH:beta:b1","5:FINISH:alpha:a1","5:START:alpha:a2","7:FINISH:alpha:a2"]The two names run concurrently. The second alpha task waits for a1, while beta finishes independently at time 3.
Example 2
operations = [["ADD","sync","s1","10"],["ADD","sync","s2","4"],["ADD","sync","s3","1"],["ADVANCE","3"],["CANCEL","sync"],["ADVANCE","4"],["ADVANCE","1"]]return = ["0:START:sync:s1","0:QUEUE:sync:s2","0:QUEUE:sync:s3","3:CANCEL:sync:s1","3:START:sync:s2","7:FINISH:sync:s2","7:START:sync:s3","8:FINISH:sync:s3"]Cancelling s1 at time 3 immediately advances the same-name queue. Its stale time-10 completion never appears.
Example 3
operations = [["ADD","red","r1","8"],["ADD","red","r2","2"],["ADD","blue","b1","4"],["ADVANCE","2"],["CLEAR","red"],["ADVANCE","2"],["CANCEL","red"],["CLEAR","red"]]return = ["0:START:red:r1","0:QUEUE:red:r2","0:START:blue:b1","2:CLEAR:red:r1","2:CLEAR:red:r2","4:FINISH:blue:b1","4:CANCEL_NONE:red","4:CLEAR_NONE:red"]Clearing red removes its running task first and then its queued task, without affecting the concurrent blue task.
Constraints
0 <= operations.length <= 100000.- Every row has one of the four exact forms above.
nameandtaskIdcontain 1 to 20 lowercase ASCII letters, digits, or underscores, and do not contain colons.- Every
taskIdin anADDoperation is globally unique. 1 <= duration <= 10^9and0 <= delta <= 10^9.- The virtual clock never exceeds
10^14. - The returned array contains at most
200000events.