MediumGreedyHeapHash TableUpdated Sep 2026

621. Task Scheduler

Asked at Google, Meta, Amazon, Microsoft and 2 more

Difficulty

Medium

Time

O(m)

Space

O(1)

Pattern

Greedy

Companies

6

Problem

You are given a list of CPU tasks. Each task is a single uppercase letter, and each task takes exactly one CPU interval to run. The CPU can also stay idle for an interval.

There is one rule: between two runs of the same task label there must be at least n other intervals (tasks or idle). You may run the tasks in any order you like.

Return the smallest number of intervals (task runs plus idle intervals) needed to finish every task.

Same task needs a gap of n

scheduleAB_AB_AB01234567The two '_' slots are idle because no other task can fill them
With n = 2, every repeat of A or B must be separated by two other intervals, so idle slots appear.

Constraints

  • ●1 <= tasks.length <= 10^4
  • ●tasks[i] is an uppercase English letter (A-Z)
  • ●0 <= n <= 100

Examples

Example 1
Inputtasks = ["A","A","A","B","B","B"], n = 2
Output8
WhyA and B each appear 3 times, so each needs 2 gaps between its runs. One valid order is A B idle A B idle A B — that is 8 intervals, and no shorter order can fit the cooldowns.
Example 2
Inputtasks = ["A","C","A","B","D","B"], n = 1
Output6
WhyWith a cooldown of 1, a task can repeat after just one other interval. A B C D A B uses all 6 tasks with no idle time, so 6 is optimal.
Example 3
Inputtasks = ["A","A","A","B","B","B"], n = 3
Output10
WhyOnly two task types exist, so gaps cannot always be filled. A B idle idle A B idle idle A B takes 10 intervals.

Asked At

6 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
LinkedInMediumView all LinkedIn questions →

How to Think About It

1

The most frequent task determines the minimum length. Calculate idle slots based on the max frequency.

2

Greedy: schedule the most frequent tasks first, then fill gaps with other tasks.

3

Formula: (maxFreq - 1) × (n + 1) + countOfMaxFreq. This accounts for the cooldown gaps between the most frequent tasks.

4

If there are enough different tasks to fill all idle slots, the answer is simply len(tasks). No idle time needed.

5

Edge cases: n=0 (return len(tasks)), single task type, all unique tasks.

Optimal Approach

Step 1: Count task frequencies.
Step 2: Find max frequency (maxFreq) and count of tasks with that frequency.
Step 3: Return max(len(tasks), (maxFreq - 1) × (n + 1) + countOfMaxFreq).

The max ensures we don't undercount when there are enough tasks to avoid idle time.

Time: O(n) — count frequencies. Space: O(1) — at most 26 task types.

Count the most frequent task

frame for AA__A__A01234563 copies of A need (3-1) blocks of size (n+1), plus one final Afill gapsAB_AB_AB01234567B has the same max frequency, so it fills one slot in each gapanswer = max(len(tasks), (maxFreq-1)*(n+1) + countMax)
The most frequent task creates the frame; other tasks fill the gaps, and leftover gaps become idle.
ComplexityTime O(m)Space O(1)m is the number of tasks; we scan the list once to count frequencies, and the counter holds at most 26 letters.

What Trips People Up in Real Interviews

1

Confusing this with "rearrange string so no two adjacent are same." That's a different problem (rearrange string). This one has a cooldown constraint.

2

Not using the formula. The minimum intervals = max(len(tasks), (maxFreq - 1) × (n + 1) + countOfMaxFreq). Don't simulate the scheduling.

3

Forgetting that the answer is at least len(tasks). If there are enough tasks to fill all gaps, no idle time is needed.

4

Not handling the case where n = 0. Return len(tasks) — no cooldown needed.

5

Miscounting tasks with max frequency. If multiple tasks share the max frequency, they all go in the last "frame." The formula adds countOfMaxFreq, not 1 — forgetting this underestimates the result.

Solution Code

O(m) time
from collections import Counter

def leastInterval(tasks, n):
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for v in freq.values() if v == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Task Scheduler problem?

Given a char array representing CPU tasks and a cooldown interval n, return the least number of intervals the CPU will take to finish all tasks. Each task takes one interval. The same task must have at least n intervals between its occurrences.

How do you solve Task Scheduler?

The optimal approach runs in O(m) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Task Scheduler?

Task Scheduler is asked at Google, Meta, Amazon, Microsoft, Apple, LinkedIn. It is a medium difficulty problem.

What are common mistakes on Task Scheduler?
  • Confusing this with "rearrange string so no two adjacent are same." That's a different problem (rearrange string). This one has a cooldown constraint.
  • Not using the formula. The minimum intervals = `max(len(tasks)`, (maxFreq - 1) × (n + 1) + countOfMaxFreq). Don't simulate the scheduling.
  • Forgetting that the answer is at least len(tasks). If there are enough tasks to fill all gaps, no idle time is needed.
  • Not handling the case where `n = 0`. Return len(tasks) — no cooldown needed.
  • Miscounting tasks with max frequency. If multiple tasks share the max frequency, they all go in the last "frame." The formula adds countOfMaxFreq, not 1 — forgetting this underestimates the result.