Problem statement

A CPU runs one task per interval (or idles). Identical tasks must be at least n intervals apart. Given tasks (letters A–Z) and the cooldown n, return the minimum number of intervals to finish all tasks.

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A → B → idle → A → B → idle → A → B.

Example 2

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6

Constraints

• 1 <= tasks.length <= 30
• 0 <= n <= 10
• tasks[i] is an uppercase letter.

Hints for Task Scheduler

1. Hint 1

   Lay out the most frequent task first: (maxFreq-1) blocks of size n+1, plus the final row.

2. Hint 2

   The answer is max(tasks.length, (maxFreq-1)*(n+1) + count of tasks with maxFreq).

How to solve Task Scheduler

The schedule's length is dictated by the most frequent task — it is the one that keeps forcing idle time. Lay it out first: maxFreq copies split the timeline into maxFreq - 1 blocks of width n + 1, plus a final row. Every other task then slots into the gaps. The only twist is that several tasks may tie for maxFreq, and each of them adds one slot to that final row.

Approach

1. Count how often each task appears.
2. Find maxFreq, the largest count, and numMax, how many tasks achieve it.
3. Compute the skeleton length: (maxFreq - 1) * (n + 1) + numMax.
4. Answer max(tasks.length, skeleton).

Why it works

The skeleton is a genuine lower bound: between consecutive runs of the most frequent task there must be at least n other intervals, giving maxFreq - 1 blocks of n + 1, and the tail holds one slot for each task tied at maxFreq. It is also achievable — filling the gaps column by column never places the same task twice within a block. When there are many distinct tasks the gaps overflow and no idling is needed at all, in which case the answer is simply the number of tasks; taking the max covers both regimes.

Complexity

• Time — O(n)
• Space — O(1) — 26 counters

Pitfalls

• Forgetting numMax under-counts whenever several tasks tie for the highest frequency.
• The max against tasks.length is essential — with many distinct tasks the formula alone is too small.
• n = 0 means no cooldown, and the formula correctly collapses to tasks.length.
• Blocks are n + 1 wide (the task itself plus n cooldown slots), not n.

Reference solution

Python

from typing import List
from collections import Counter

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

Java

public static int leastInterval(String[] tasks, int n) {
    int[] count = new int[26];
    for (String t : tasks) count[t.charAt(0) - 'A']++;
    int maxFreq = 0, numMax = 0;
    for (int c : count) {
        if (c > maxFreq) {
            maxFreq = c;
            numMax = 1;
        } else if (c == maxFreq && c > 0) {
            numMax++;
        }
    }
    int skeleton = (maxFreq - 1) * (n + 1) + numMax;
    return Math.max(tasks.length, skeleton);
}

C++

int leastInterval(vector<string>& tasks, int n) {
    int count[26];
    for (int i = 0; i < 26; i++) count[i] = 0;
    for (const string& t : tasks) count[t[0] - 'A']++;
    int maxFreq = 0, numMax = 0;
    for (int i = 0; i < 26; i++) {
        if (count[i] > maxFreq) {
            maxFreq = count[i];
            numMax = 1;
        } else if (count[i] == maxFreq && count[i] > 0) {
            numMax++;
        }
    }
    int skeleton = (maxFreq - 1) * (n + 1) + numMax;
    return max((int) tasks.size(), skeleton);
}

JavaScript

var leastInterval = function(tasks, n) {
    const count = new Map();
    for (const t of tasks) count.set(t, (count.get(t) || 0) + 1);
    const freqs = Array.from(count.values());
    const maxFreq = Math.max.apply(null, freqs);
    const maxCount = freqs.filter(function(f) { return f === maxFreq; }).length;
    return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium