Task Scheduler

Medium20–25 min

Topics

HashMapGreedyCountingArray

Companies

AmazonBloombergFacebook

You are given a list of tasks, each identified by a single uppercase letter, and a non-negative integer n — the number of full time units that must pass after running a task before another task of that exact same type can run again. Each time unit, the CPU can either execute one task or sit idle. Find the minimum number of time units needed to finish every task in the list while respecting the cooldown between two tasks of the same type.

Test Case 1:

Input:tasks = [X, X, X, Y, Y, Z], n = 2

Output:7

Explanation:X needs a gap of 2 after every run, so the schedule is X, Y, Z, X, Y, idle, X.

Test Case 2:

Input:tasks = [M], n = 3

Output:1

Explanation:A single task needs no cooldown.

Test Case 3:

Input:tasks = [P, Q, P, Q], n = 1

Output:4

Explanation:There are enough distinct tasks to fill every gap — no idle time needed.

Constraints

◆1 ≤ tasks.length ≤ 50
◆tasks[i] is a single uppercase English letter ('A' to 'Z')
◆0 ≤ n ≤ 20

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Greedy Minute-by-Minute Simulation

Good

Simulate the CPU one time unit at a time. At every tick, look at the task types whose cooldown has already expired and run whichever one still has the most instances left — keeping the busiest type moving prevents it from piling up scarcity later. If nothing is available, the CPU sits idle for that tick. Stop once every instance of every task has run. This mirrors the process directly and is easy to trust, but it re-scans all 26 possible task types on every single tick, so its runtime tracks the length of the final schedule rather than just the size of the input.

TimeO(n · maxFreq)

SpaceO(1)

Java

Try it out

class Solution {
    public int taskScheduler(String[] tasks, int n) {
        int[] count = new int[26];
        for (String task : tasks) {
            count[task.charAt(0) - 'A']++;
        }
        int[] nextAvailable = new int[26];
        int remaining = tasks.length;
        int time = 0;
        while (remaining > 0) {
            int best = -1;
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0 && nextAvailable[i] <= time) {
                    if (best == -1 || count[i] > count[best]) best = i;
                }
            }
            if (best != -1) {
                count[best]--;
                remaining--;
                nextAvailable[best] = time + n + 1;
            }
            time++;
        }
        return time;
    }
}

Optimal — Frequency Count + Closed-Form Gap Filling

Optimal

Count how many times each task type appears. The type with the highest count, maxFreq, forces maxFreq - 1 mandatory cooldown gaps of length n + 1 between its own occurrences (the very last occurrence needs no trailing gap). Every other task type can slot into those gaps to fill idle time — including any other type that's also tied at maxFreq, which can only add one more instance each, at the very end. That gives (maxFreq - 1) * (n + 1) + maxCount as the minimum time needed to satisfy the cooldown. But if there are enough distinct tasks to fill every single gap with no idle time left over, the true answer is simply the number of tasks — so the final answer is whichever of the two is larger.

TimeO(len(tasks))