The Runtime Theory
mediumleetcode#sorting#min-heap#simulation

Simulate a Single-Threaded CPU Scheduler

Use an arrival-time queue and a shortest-processing-time priority queue to schedule ready tasks without preemption.

The Runtime Theory Team1 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

intasks=[[1,2],[2,4],[3,2],[4,1]]

out[0,2,3,1]

intasks=[[7,10],[7,12],[7,5],[7,4],[7,2]]

out[4,3,2,0,1]

Each task has an enqueue time and processing duration. A single CPU runs one ready task at a time. When idle, it selects the available task with the shortest processing time; ties go to the smaller original index. Tasks arriving while the CPU is busy wait in the ready queue.

Sort tasks by enqueue time and maintain a min-heap ordered by (duration, originalIndex). If the heap is empty, advance the simulated clock to the next task arrival. Otherwise pop one ready task, advance by its duration, and add every task that arrived by the new time.

Use a 64-bit or otherwise sufficiently wide clock so accumulated durations cannot overflow. Trace a case where the CPU becomes idle between arrivals and one where several tasks arrive during one execution. The problem is a scheduling simulation, not a complete model of a real kernel scheduler.

More practice in this topic

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save