How should I practice Timer Job Scheduler Wake-ups?

Start by reading the full statement, solve the visible examples, then compare the pattern against related RedNote phone screen problems in FastPrep.

Is Timer Job Scheduler Wake-ups associated with RedNote?

FastPrep tags this as a RedNote phone screen coding practice problem when the problem catalog has that company and stage context.

Timer Job Scheduler Wake-ups

RedNote● MediumFULLTIMEPHONE SCREEN

Problem statement

A job scheduler keeps timed jobs in a priority queue. The job with the earliest run time is the head; jobs with the same run time are ordered by when they were added. The scheduler sleeps between wake-ups and wakes up in two ways:

New head. When an added job becomes the head of the queue (the queue was empty, or its run time is earlier than the current head's), the add wakes the scheduler right away. A job with the same run time as the head goes behind it and does not wake the scheduler.
Timer. Otherwise the scheduler sleeps until a timer set to the head's run time wakes it.

Every time the scheduler wakes up at time t, it hands every job whose run time is at most t to the workers, in queue order, and removes them from the queue. Then it sets the timer to the new head's run time, if there is one, and goes back to sleep. Workers are always free.

You are given the jobs in the order they are added. jobs[i] = [addTime, jobId, runAt] means job jobId is added at addTime to run at runAt. If the timer goes off at the same moment a job is added, the timer wake-up happens first. After the last job is added, the scheduler keeps running until every job has been handed out.

Return every wake-up in order. Record a wake-up as [t, cause, id1, id2, ...]: the time, then 1 if a new head woke the scheduler or 0 if the timer did, then the ids of the jobs handed out during that wake-up, in order. A wake-up can hand out no jobs.

Discussion

In a real scheduler, the add and the timer run on different threads. How would you wait on the timer so that an add can wake the scheduler early? This is for discussion; the tests check only the returned wake-ups.

Function

schedulerWakeups(jobs: int[][]) → int[][]

Examples

Example 1

jobs = [[0,1,10],[2,2,5],[3,3,7],[8,4,8]]return = [[0,1],[2,1],[5,0,2],[7,0,3],[8,1,4],[10,0,1]]

At time 0, job 1 goes into an empty queue, so it is the new head and wakes the scheduler: [0, 1]. Nothing is due, and the timer is set for 10. At time 2, job 2 (due at 5) becomes the new head, wakes the scheduler, [2, 1], and the timer moves to 5. At time 3, job 3 (due at 7) is not the head, so nothing wakes. The timer wakes the scheduler at 5 for job 2 and at 7 for job 3. At time 8, job 4 is due right away and is the new head, so it wakes the scheduler and is dispatched at once: [8, 1, 4]. Finally the timer fires at 10 for job 1.

Example 2

jobs = [[0,7,4],[1,8,4],[2,9,4]]return = [[0,1],[4,0,7,8,9]]

Job 7 wakes the scheduler at time 0 and sets the timer for 4. Jobs 8 and 9 are due at the same time as the head, so neither becomes the head and neither wakes the scheduler. At 4 the timer wakes the scheduler once, and all three due jobs are dispatched in the order they were added.

Example 3

jobs = [[5,3,9],[9,4,12]]return = [[5,1],[9,0,3],[9,1],[12,0,4]]

Job 3 wakes the scheduler at 5. At time 9, the timer fires before job 4 is added, so job 3 is dispatched first: [9, 0, 3]. Then job 4 arrives at an empty queue and wakes the scheduler: [9, 1]. The timer fires at 12 for job 4.

Constraints

1 <= jobs.length <= 500
Each jobs[i] is [addTime, jobId, runAt].
0 <= addTime <= runAt <= 10^9
jobs is sorted by addTime (equal times are allowed and are handled in the given order).
1 <= jobId <= 10^6, and all job ids are different.