Task Scheduler

Master this topic with zero to advance depth.

Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. For each unit of time, the CPU could complete either one task or stay idle.

There is a cooldown period n between two same tasks, meaning at least n units of time must pass between any two executions of the same task.

Return the least number of units of time to finish all tasks.

Visual Representation

tasks = ["A","A","A","B","B","B"], n = 2

Timeline:
A -> B -> idle -> A -> B -> idle -> A -> B
1    2    3       4    5    6       7    8

Total Time: 8

Medium

Examples

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

Approach 1

Level I: Simple Simulation

Intuition

At each unit of time, we want to pick the most frequent task that is currently available (not in cooldown). We can simulate this step-by-step.

Thought Process

Count frequencies of all tasks.
Maintain an array nextAvailableTime for each task.
At each time t, pick the available task with the highest remaining frequency.
If no task is available, stay idle and increment time.

⏱ O(TotalTime * 26)💾 O(1)

Detailed Dry Run

tasks=[A,A,B], n=2 t=0: best=A (count 2). nextAvail[A]=3, rem=2. t=1: best=B (count 1). nextAvail[B]=4, rem=1. t=2: no one avail (A needs t=3). idle. t=3: best=A (count 1). nextAvail[A]=6, rem=0. Total: 4 units.

java

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

Approach 2

Level II: Greedy with Max-Heap

Intuition

Instead of scanning all tasks every time, we use a Max-Heap to always pick the highest frequency task. Tasks in cooldown are stored in a temporary wait-queue and added back to the heap once their cooldown expires.

Thought Process

Push all task frequencies into a Max-Heap.
Use a Queue to store {remaining_freq, release_time} for tasks in cooldown.
At each unit of time:
- Check the Queue: If a task's release_time <= current_time, push it back to the Heap.
- Pop the highest frequency task from the Heap, decrement its frequency, and if it's still > 0, add it to the wait-queue with release_time = current_time + n + 1.

Pattern: Priority Queue Simulation

⏱ O(N log 26)💾 O(1) - Heap and Queue size are capped at 26.

Detailed Dry Run

tasks=[A,A,A,B,B,B], n=2 Heap: [(A,3), (B,3)] t=0: Pop (A,3). Add to waitQueue: (A,2) at t=3. time=1. t=1: Pop (B,3). Add to waitQueue: (B,2) at t=4. time=2. t=2: Heap empty. Wait till t=3... time=3. t=3: WaitQueue release (A,2). Heap: [(A,2)]...

java

import java.util.*;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] counts = new int[26];
        for (char t : tasks) counts[t - 'A']++;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int c : counts) if (c > 0) maxHeap.add(c);

        Queue<int[]> waitQueue = new LinkedList<>();
        int time = 0;
        while (!maxHeap.isEmpty() || !waitQueue.isEmpty()) {
            time++;
            if (!waitQueue.isEmpty() && waitQueue.peek()[1] == time) {
                maxHeap.add(waitQueue.poll()[0]);
            }
            if (!maxHeap.isEmpty()) {
                int cnt = maxHeap.poll() - 1;
                if (cnt > 0) waitQueue.add(new int[]{cnt, time + n + 1});
            }
        }
        return time;
    }
}

Approach 3

Level III: Optimal Frequency Analysis (Math)

Intuition

The total time is bounded by the most frequent task. If 'A' is the most frequent (frequency $f$ ), we have $f$ blocks. Each of the first $f-1$ blocks must be followed by $n$ slots (either other tasks or idle).

Thought Process

Let max_f be the maximum frequency.
The base structure is (max_f - 1) * (n + 1) slots.
Any other tasks with the same max_f frequency will fill one extra slot at the very end.
Total time = (max_f - 1) * (n + 1) + num_tasks_with_max_f.
If this result is smaller than the total number of tasks, it means no idle slots are needed, so the answer is tasks.length.

Pattern: Math / Frequency Analysis

⏱ O(N) - Single pass to count frequencies.💾 O(1) - Constant space for 26 frequencies.

Detailed Dry Run

tasks = [A,A,A,B,B,B], n = 2

Variable	Value	Explanation
maxFreq	3	'A' and 'B' both appear 3 times
countMax	2	Two tasks (A, B) have max frequency
Formula	(3-1)*(2+1) + 2	2 * 3 + 2 = 8
Final	max(8, 6)	8

Visualization:

[A, B, _] [A, B, _] [A, B] -> Total 8 slots.

java

import java.util.Arrays;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freqs = new int[26];
        for (char t : tasks) freqs[t - 'A']++;
        Arrays.sort(freqs);
        
        int maxFreq = freqs[25];
        int countMax = 0;
        for (int f : freqs) if (f == maxFreq) countMax++;

        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMax);
    }
}

← Previous QuestionQueue Reconstruction by Height

Next Question →Minimum Number of Taps to Water Garden

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.