Task Scheduler

Round-robin with cooldown

time O(n * N)space O(N)

The insight: the task with the highest remaining count is the real bottleneck — it needs cooldown gaps of length n between its own occurrences no matter what, so the only way to avoid wasted time is to fill those gaps with other eligible tasks before they run out. Greedily running whichever tasks have the highest remaining count each cycle keeps every slot busy for as long as possible; only when every task is still on cooldown do you have no choice but to burn an idle slot. That's why total time is driven by the most frequent task's spacing requirement, not by simply summing up task counts.

Details

Animated on: Schedule tasks with cooldown period n minimizing total time

Problem:Task SchedulerMedium

Pattern:Greedy Scheduling and Sorting

Round-robin with cooldown

step 1 / 9

[0]

[1]

[2]

[3]

[4]

[5]

Initialize: count A=3, B=3. Max-heap [A:3, B:3]. Cooldown n=2. Time starts at 0.

count=0· arr[0] = A

Pseudocode

1FUNCTION taskScheduler(tasks, n):
2  cnt = a lookup table (task → its remaining count)
3  FOR each task t in tasks: add one to cnt[t]
4  h = a max-heap of counts (busiest task on top)
5  time = 0
6  WHILE h is not empty: run one cycle of up to n+1 slots — pop the highest-count tasks, decrease each by one, keep the ones still > 0 aside, then push them back; add the slots used (idle slots count too) to time
7  RETURN time
8END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 9 steps

Initialize: count A=3, B=3. Max-heap [A:3, B:3]. Cooldown n=2. Time starts at 0.
Execute A (first). Count A→2. Heap: [B:3, A:2]. Time: 1. Cooldown: A for 2 slots.
Execute B (first). Count B→2. Heap: [A:2, B:2]. Time: 2. Both tasks on cooldown.
Cooldown slot 1 of 2. A and B both cooling. No executable tasks. Idle slot. Time: 3.
A available again. Execute A (second). Count A→1. Heap: [B:2, A:1]. Time: 4.
Execute B (second). Count B→1. Heap: [A:1, B:1]. Time: 5.
Cooldown slot 2 of 2. A and B both cooling. No executable tasks. Idle slot. Time: 6.
A available again. Execute A (third). Count A→0. Heap: [B:1, A:0]. Time: 7.
Execute B (third). Count B→0. All tasks complete. Total time: 8. Final answer: minimum time = 8.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Task Scheduler in the editor All Heap problems Back to roadmap