Task Scheduler

mediumHeap / Priority Queue125 stepsJava · Python · C++

Tasks of the same type need n idle slots between them. The most frequent task decides the shape: it creates maxFreq - 1 gaps of size n. Fill them with other tasks; if there are more tasks than slots, no idling is needed and the answer is the task count.

▶ Watch the animated trace

Traced input: tasks = [A, A, A, B, B, B], n = 2 → 8. Original problem: neetcode.io/problems/task-scheduling

Complexity

BestO(N)

AverageO(N)

WorstO(N)

SpaceO(1)

Counting 26 letters; the formula is O(1) after that.

Key idea

Lay out the most frequent task with n slots after each: (maxFreq - 1) × (n + 1) frames.
Tasks tied for the max frequency fill the final frame: add countMax.
If tasks outnumber the frames, there are no idle slots: answer is tasks.length.

Common mistakes

Forgetting the max(tasks.length, …) part.
Counting only one task with the maximum frequency.
A max-heap simulation also works and is good to explain; the formula is faster.

Solution

Java

int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];
    for (char t : tasks) count[t - 'A']++;
    int maxFreq = 0;
    for (int c : count) maxFreq = Math.max(maxFreq, c);
    int countMax = 0;
    for (int c : count) if (c == maxFreq) countMax++;
    int frames = (maxFreq - 1) * (n + 1) + countMax;
    int result = Math.max(tasks.length, frames);
    return result;
}

Python

def leastInterval(tasks: List[str], n: int) -> int:
    count = Counter(tasks)
    max_freq = max(count.values())
    count_max = sum(1 for c in count.values() if c == max_freq)
    frames = (max_freq - 1) * (n + 1) + count_max
    return max(len(tasks), frames)

C++

int leastInterval(vector<char>& tasks, int n) {
    int count[26] = {0};
    for (char t : tasks) count[t - 'A']++;
    int maxFreq = *max_element(count, count + 26);
    int countMax = 0;
    for (int c : count) if (c == maxFreq) countMax++;
    int frames = (maxFreq - 1) * (n + 1) + countMax;
    return max((int)tasks.size(), frames);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No cooldown Run back to back.	`tasks = [A, A, A, B, B, B], n = 0`	`6`
Plenty of variety Enough different tasks to fill every gap.	`tasks = [A, B, C, D, E, A, B, C, D, E], n = 2`	`10`
One task type A _ _ _ A _ _ _ A.	`tasks = [A, A, A], n = 3`	`9`
Single task No repeats, no idling.	`tasks = [A], n = 5`	`1`