621. Task Scheduler

621

MediumHeap and Priority QueueGreedy counting (max-heap simulation equivalent)Fill idle slots around the most frequent task

Task Scheduler

Given a list of CPU tasks labeled by letters and an integer n, each task takes one unit of time and identical tasks must be separated by at least n units of cooldown. In each unit the CPU either runs one task or stays idle. Return the minimum number of time units needed to finish all tasks.

Open official problem prompt ↗

In plain English

Compute the shortest possible schedule length that runs every task exactly once while never repeating a task within n units, inserting idle slots only when unavoidable.

Picture it like this

Seating repeated guests at a long table where the same family must be at least n chairs apart. The largest family sets the spacing; smaller families fill the chairs in between, and you only leave chairs empty when there simply are not enough other guests to fill the required gaps.

Example

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Why: A valid schedule is A B idle A B idle A B, taking 8 units — the two idles are forced by the cooldown of 2 between repeats of A.

Constraints

1 <= tasks.length <= 10^4tasks[i] is an uppercase English letter0 <= n <= 100

Pattern lesson

See the pattern, then code

Fill idle slots around the most frequent task

↗

Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. The busiest task dictates the skeleton: place its copies n+1 apart, forming (maxCount-1) frames of width n+1, then a final block. Every other task slots into the gaps. If there are more tasks than gap slots, they pack in with no idle time, so the answer is simply the task count.

New words, made simpleKnow these before the algorithm

Cooldown n: The minimum number of intervals between two runs of the same task.
Frame: A block of width n+1 anchored by one copy of the most frequent task.
Idle: A time unit where the CPU runs nothing because every remaining task is still cooling down.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Max-heap simulation

Directly models the process and is a great heap exercise, but more code and easy to get the cooldown queue wrong.

Repeatedly run the highest-count ready task, park it in a cooldown queue for n steps, tick time forward including idles.

Time O(N) with a bounded 26-element heapSpace O(1)

Best choiceGreedy frame formula

Constant extra space and a single closed-form answer; simplest to prove and implement.

Arrange around the most frequent task's frames and fill gaps, taking the max with the raw task count.

Time O(N)Space O(1)

The rule we keep true

Invariant

The most frequent task forces (maxCount-1) fully separated frames of length n+1; all remaining tasks either fit inside those frames' gaps or, if they overflow, eliminate every idle slot.

Why this is correct

Reasoning

Placing the busiest task with exactly n+1 spacing is both necessary (any tighter violates cooldown) and sufficient (nothing forces wider gaps). Other tasks drop into the gaps; when their count exceeds the gap capacity, they can always be interleaved with no idle, and the total is then just len(tasks) — which the max() captures.

The algorithm in three movesSay these aloud before coding

1Count each task's frequency

counts: A=3, B=3

2Find the maximum frequency maxCount and how many tasks share it (countMax)

maxCount=3, countMax=2

3Compute the framed length (maxCount-1)*(n+1)+countMax

frame = (3-1)*(2+1)+2 = 8

4Return the larger of that value and the total number of tasks

max(8, 6 tasks) = 8

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readtasks

2 · AskFrequencies?

3 · Update stateA=3, B=3

4 · ResultTwo tasks tie for busiest.

Key takeaway

Schedule skeleton: A anchors each frame, B fills the gaps, underscores are idle.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6Tally frequencies
Counter gives each task's occurrence count in one pass.
2
Lines 7Find the peak
The most frequent task determines the number and width of frames.
3
Lines 8Count the ties
Tasks sharing the peak frequency all appear in the final block, adding countMax to the tail.
4
Lines 9Take the max
When many distinct tasks fill every gap, no idle is needed and the answer is simply len(tasks).

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 0 (no cooldown, answer is len(tasks))
All tasks identical, e.g. all A (answer stretches to (count-1)*(n+1)+1)
More distinct tasks than gap slots (answer equals total task count)
A single task

Common beginner mistakes

Forgetting the max() with len(tasks), which underestimates when tasks overflow the frames
Using (maxCount-1)*n instead of (maxCount-1)*(n+1), dropping the anchor slot
Counting only one peak task when several share the maximum frequency
Assuming idles always appear — with enough variety there are none

Check your understanding

Why does the answer become exactly len(tasks) once there are enough distinct tasks, regardless of n?

Task Scheduler

Task Scheduler

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Heap and Priority Queue