Task Scheduler

For Task Scheduler, the key move is to count how often each task appears, then measure how the most frequent task creates forced cooldown blocks. The minimum answer is the larger of total task count and the frame-based formula built from the maximum frequency. This avoids slow simulation and directly explains why tasks like ["A","A","A","B","B","B"] with n = 2 need 8 intervals.

Problem Statement

You need to schedule CPU tasks labeled A to Z. In each interval, the CPU can either run one task or stay idle. The tricky part is the cooldown rule: after running a task with some label, you cannot run that same label again until at least n other intervals have passed.

Return the smallest number of intervals needed to finish every task. For example, with tasks = ["A","A","A","B","B","B"] and n = 2, the answer is 8 because the repeated high-frequency tasks create forced gaps, and some of those gaps become idle time when there are not enough other tasks to fill them.

Examples

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B. After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3 rd interval, neither A nor B can be done, so you idle. By the 4 th interval, you can do A again as 2 intervals have passed.

Example 2

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

A possible sequence is: A -> B -> C -> D -> A -> B. With a cooling interval of 1, you can repeat a task after just one other task.

Example 3

Input: tasks = ["A","A","A", "B","B","B"], n = 3

Output: 10

A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B. There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints

• 1 <= tasks.length <= 104
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

Solution Approach

Count frequencies before thinking about order

Start with an array or hash map that counts how many times each task appears. In Task Scheduler, the exact order is flexible, so the real bottleneck is not adjacency scanning but identifying which task label appears most often. That maximum frequency determines how many cooldown-separated blocks the schedule must support.

Build the greedy frame from the most frequent task

If the highest frequency is maxFreq, imagine placing those copies first. They create maxFreq - 1 full gaps between them, and each gap needs length n. That gives a frame size of (maxFreq - 1) * (n + 1). If multiple task labels share the same maxFreq, they occupy the tail positions of those frames, so add maxCount, the number of labels tied for maximum frequency. The formula becomes (maxFreq - 1) * (n + 1) + maxCount.

Take the maximum of frame size and total tasks

The frame formula tells you the minimum schedule length when cooldown pressure actually forces idle slots. But if there are enough other tasks to fill every gap, the CPU never idles and the answer is just tasks.length. So the final result is max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount). This is why the classic example returns 8 instead of 6: the repeated A and B tasks leave unavoidable empty intervals.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(26)

Counting all tasks takes O(N), and scanning the 26 uppercase letters to find maxFreq and maxCount is constant work, so the full solution is O(N) time and O(26) space. The constant-space detail matters here because Task Scheduler only uses capital letters, which lets the counting structure stay fixed-size instead of growing with input length.

What Interviewers Usually Probe

• They want you to stop simulating interval by interval and recognize that the most frequent task controls the schedule length.
• They are checking whether you can turn cooldown spacing into a counting formula instead of using a heap for every interval.
• They may ask why the answer is max(total tasks, frame formula), which tests whether you understand when idle slots disappear.

Common Pitfalls or Variants

Common pitfalls

• Using only the single maximum frequency and forgetting maxCount, which breaks cases where several task labels tie for the top count.
• Simulating a full schedule with sorting or a heap without noticing that LeetCode 621 has a direct counting solution.
• Returning the frame formula directly even when many remaining tasks fill all cooldown gaps, causing an overestimate.

Follow-up variants

• Solve the same Task Scheduler input with a max heap simulation to show the schedule explicitly instead of only returning its length.
• Change the problem so each task label has a different cooldown, which removes the simple closed-form formula.
• Ask for the actual task order with idles included, which turns the counting shortcut into a construction problem.

FAQ

What is the main pattern behind Task Scheduler?

The core pattern is counting frequencies, then using a greedy frame formula based on the task labels with the highest count. Even though many valid schedules exist, the minimum interval count is controlled by cooldown gaps around the most frequent tasks.

Why is the answer not always just tasks.length?

When repeated high-frequency tasks need long cooldown gaps, there may not be enough other tasks to fill those slots. In that case, idle intervals become mandatory, so the answer grows beyond the raw number of tasks.

Why do we use maxCount in the formula?

If multiple task labels are tied for the highest frequency, they all occupy the final positions of the cooldown frames. Ignoring that tie causes the schedule length to be too small on cases like several letters appearing equally often.

Can Task Scheduler be solved with a heap instead?

Yes. A max heap plus cooldown tracking can simulate the process and is useful when you need the actual order. But for LeetCode 621, the counting formula is simpler and faster because the problem only asks for the minimum number of intervals.

How does the array scanning plus hash lookup pattern fit this problem?

You scan the task array once to build counts with an array or hash lookup, then scan those counts to find the highest frequency and how many labels reach it. That small amount of counting logic replaces a much more expensive interval-by-interval scheduling attempt.