68.Task Scheduler

MediumHeap / Priority Queue · 5/7

Problem

You are given an array of CPU tasks tasks, each labeled with an uppercase letter, and a non-negative integer n. Each time unit the CPU either runs one task or stays idle. Two runs of the same task label must be separated by at least n time units.

Tasks may be executed in any order. Return the minimum number of time units needed to finish all tasks.

Examples

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

Input:  tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A -> B -> C -> D -> A -> B. No idle needed.

Input:  tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints

1 <= tasks.length <= 10^4
tasks[i] is an uppercase English letter.
0 <= n <= 100

💡 Key Insight

Only the counts of each letter matter. The most frequent task dictates the skeleton: with frequency maxFreq, it creates maxFreq - 1 full "frames" of length n + 1, plus a final partial frame containing every task that also has frequency maxFreq. Everything else fills the idle slots; if there are more tasks than slots, there is no idle time at all and the answer is simply tasks.length.

Brute Force (Greedy Simulation per Time Unit)

TimeO(T · 26) where T is the answer (at most tasks.length · (n + 1)).SpaceO(1)

Intuition

Simulate the CPU clock. At each time unit, among the tasks that are off cooldown, run the one with the most remaining occurrences (running frequent tasks early avoids being stuck with only one task type at the end). If nothing is available, idle.

Algorithm

Count each letter into count[26]; nextFree[26] = 0.
time = 0, remaining = tasks.length.
While remaining > 0: find best with count > 0, nextFree <= time and maximum count.
- If found: count[best]--, nextFree[best] = time + n + 1, remaining--.
- time++ (whether or not a task ran).
Return time.

Visualization

counts A=3, B=3, n=2
t=0: A,B ready  -> run A (nextFree A = 3)
t=1: B ready    -> run B (nextFree B = 4)
t=2: none ready -> idle
t=3: A ready    -> run A
t=4: B          -> run B
t=5: idle
t=6: A, t=7: B  -> time = 8

Code

java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks) {
            count[t - 'A']++;
        }
        int[] nextFree = new int[26]; // earliest time each task may run again
        int remaining = tasks.length;
        int time = 0;
        while (remaining > 0) {
            int best = -1;
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0 && nextFree[i] <= time && (best == -1 || count[i] > count[best])) {
                    best = i;
                }
            }
            if (best != -1) {
                count[best]--;
                nextFree[best] = time + n + 1;
                remaining--;
            }
            time++; // a task or an idle slot consumed this unit
        }
        return time;
    }
}

Complexity

Time: O(T · 26) where T is the answer (at most tasks.length · (n + 1)).
Space: O(1) — two arrays of size 26.

Max-Heap + Cooldown Queue

TimeO(T · log 26) = O(T)SpaceO(1)

Intuition

The same greedy, but organized with data structures: a max-heap holds the remaining counts of tasks that are ready, and a FIFO queue holds [remainingCount, readyTime] for tasks on cooldown. Each tick, run the largest ready count, and move a task back from the queue to the heap when its cooldown expires.

Algorithm

Push every non-zero letter count into a max-heap.
time = 0. While heap or queue is non-empty:
- time++.
- If heap is non-empty: c = poll() - 1; if c > 0, enqueue [c, time + n].
- If the queue head's readyTime == time, move its count back into the heap.
Return time.

Visualization

tasks = A×3, B×3, n = 2:

flowchart TD
    T1["t=1 run A<br/>heap {3} queue [A2@3]"] --> T2["t=2 run B<br/>heap {} queue [A2@3, B2@4]"]
    T2 --> T3["t=3 idle<br/>A2 ready -> heap {2}"]
    T3 --> T4["t=4 run A<br/>B2 ready -> heap {2}"]
    T4 --> T5["t=5 run B<br/>queue [A1@6, B1@7]"]
    T5 --> T6["t=6 idle, A1 ready"]
    T6 --> T7["t=7 run A, B1 ready"]
    T7 --> T8["t=8 run B<br/>all empty -> 8"]

Code

java

import java.util.ArrayDeque;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks) {
            count[t - 'A']++;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int c : count) {
            if (c > 0) {
                maxHeap.offer(c);
            }
        }
        Queue<int[]> cooldown = new ArrayDeque<>(); // [remaining count, time it becomes ready]
        int time = 0;
        while (!maxHeap.isEmpty() || !cooldown.isEmpty()) {
            time++;
            if (!maxHeap.isEmpty()) {
                int left = maxHeap.poll() - 1;
                if (left > 0) {
                    cooldown.offer(new int[] {left, time + n});
                }
            }
            if (!cooldown.isEmpty() && cooldown.peek()[1] == time) {
                maxHeap.offer(cooldown.poll()[0]); // cooldown finished
            }
        }
        return time;
    }
}

Complexity

Time: O(T · log 26) = O(T) — at most 26 entries in the heap; T is the answer.
Space: O(1) — heap and queue hold at most 26 entries.

Math / Counting FramesOptimal

TimeO(m) where m = tasks.lengthSpaceO(1)

Intuition

Let maxFreq be the highest count and maxCount the number of letters having that count. Lay out the most frequent task(s) in rows of width n + 1:

n = 2, A x3, B x3, C x1

A B C     <- frame 1 (width n+1 = 3)
A B _     <- frame 2
A B       <- last row: only tasks with maxFreq (maxCount = 2)

(maxFreq - 1) * (n + 1) + maxCount = 2 * 3 + 2 = 8

Other tasks fill the gaps. If they overflow the gaps, the rows simply get wider with no idle at all, so the answer becomes tasks.length. Hence max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount).

Algorithm

Count letters; find maxFreq.
maxCount = number of letters with count maxFreq.
Return max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount).

Dry Run

flowchart LR
    A["tasks: A x6, B..G x1<br/>n = 2"] --> B["maxFreq = 6<br/>maxCount = 1"]
    B --> C["(6-1) * 3 + 1 = 16"]
    C --> D{"16 vs 12 tasks"}
    D -->|"max"| E["answer 16"]

Code

java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        int maxFreq = 0;
        for (char t : tasks) {
            maxFreq = Math.max(maxFreq, ++count[t - 'A']);
        }
        int maxCount = 0; // how many letters share the top frequency
        for (int c : count) {
            if (c == maxFreq) {
                maxCount++;
            }
        }
        int framed = (maxFreq - 1) * (n + 1) + maxCount;
        return Math.max(tasks.length, framed); // no idle if tasks overflow the frames
    }
}

Complexity

Time: O(m) where m = tasks.length — one counting pass plus 26 checks.
Space: O(1) — a 26-element array.

Complexity Comparison

Approach	Time	Space
Greedy Simulation	O(T · 26)	O(1)
Max-Heap + Cooldown Queue	O(T)	O(1)
Counting Frames	O(m)	O(1)

Common Pitfalls

Forgetting the max(tasks.length, ...) — with many distinct tasks (e.g. n = 1, six different letters) the formula alone underestimates.
Counting only one task in the last frame when several letters tie for maxFreq.
Cooldown off-by-one: a task run at time t may run again at t + n + 1, not t + n.
In the simulation, picking any ready task instead of the one with the most remaining — that can strand the frequent task at the end and add unnecessary idles.