Task Scheduler

Problem Description

You are given an array of CPU tasks tasks, where tasks[i] is an uppercase English letter. Each letter represents a different category. The CPU must execute each task but can rest between tasks. There is a non-negative integer n that represents the cooldown interval between two same tasks.

Return the minimum number of intervals (steps) required to finish all tasks.

Examples

Constraints

• 1 ≤ tasks.length ≤ 10⁴
• tasks[i] is an uppercase English letter
• 0 ≤ n ≤ 100

Always Execute the Most Frequent Task Next

The bottleneck is the most frequent task. If it appears maxFreq times, it needs maxFreq - 1 gaps of size n between its executions. Other tasks fill those gaps; if there aren’t enough, idle time fills them.

Math formula: result = max(tasks.length, (maxFreq - 1) * (n + 1) + countOfMaxFreq). The first term is when tasks are dense enough to eliminate idle time. The second term accounts for structured gaps around the most frequent task.

The heap simulation approach is more general and easier to derive on-the-fly in an interview.

Solution 1: Greedy Formula

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char t : tasks) freq[t - 'A']++;

        int maxFreq = 0;
        for (int f : freq) maxFreq = Math.max(maxFreq, f);

        // count how many tasks share the maximum frequency
        int countOfMax = 0;
        for (int f : freq) if (f == maxFreq) countOfMax++;

        int minIntervals = (maxFreq - 1) * (n + 1) + countOfMax;
        return Math.max(tasks.length, minIntervals);
    }
}

from collections import Counter

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        freq = Counter(tasks)
        max_freq = max(freq.values())
        count_of_max = sum(1 for f in freq.values() if f == max_freq)

        min_intervals = (max_freq - 1) * (n + 1) + count_of_max
        return max(len(tasks), min_intervals)

#include <vector>
#include <algorithm>

class Solution {
public:
    int leastInterval(std::vector<char>& tasks, int n) {
        std::vector<int> freq(26, 0);
        for (char t : tasks) freq[t - 'A']++;

        int maxFreq = *std::max_element(freq.begin(), freq.end());
        int countOfMax = std::count(freq.begin(), freq.end(), maxFreq);

        int minIntervals = (maxFreq - 1) * (n + 1) + countOfMax;
        return std::max((int)tasks.size(), minIntervals);
    }
};

Complexity Analysis:

• Time Complexity: O(m) where m is the number of tasks. Computing frequency is O(m), finding max is O(1) (26 fixed letters).
• Space Complexity: O(1) for the 26-element frequency array.

Where it breaks: the formula works because tasks fill the idle slots in the structured schedule. It gives the correct minimum in all cases, but it’s not obvious why during an interview without deriving it step by step.

Solution 2: Max-Heap + Queue Simulation

Simulate the scheduler directly: always pick the highest-frequency available task. Use a max-heap for current available tasks and a queue to hold tasks in cooldown.

import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char t : tasks) freq[t - 'A']++;

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int f : freq) if (f > 0) maxHeap.offer(f);

        // queue holds [remaining_count, available_at_time]
        Queue<int[]> cooldown = new LinkedList<>();
        int time = 0;

        while (!maxHeap.isEmpty() || !cooldown.isEmpty()) {
            time++;
            if (!maxHeap.isEmpty()) {
                int count = maxHeap.poll() - 1;
                if (count > 0) cooldown.offer(new int[]{count, time + n});
            }
            if (!cooldown.isEmpty() && cooldown.peek()[1] == time) {
                maxHeap.offer(cooldown.poll()[0]);
            }
        }

        return time;
    }
}

import heapq
from collections import Counter, deque

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        freq = Counter(tasks)
        max_heap = [-f for f in freq.values()]
        heapq.heapify(max_heap)

        cooldown = deque()  # (remaining_count, available_at_time)
        time = 0

        while max_heap or cooldown:
            time += 1
            if max_heap:
                count = heapq.heappop(max_heap) + 1  # +1 because stored negative
                if count < 0:  # still tasks remaining for this type
                    cooldown.append((count, time + n))

            if cooldown and cooldown[0][1] == time:
                heapq.heappush(max_heap, cooldown.popleft()[0])

        return time

#include <vector>
#include <queue>
#include <deque>
#include <algorithm>

class Solution {
public:
    int leastInterval(std::vector<char>& tasks, int n) {
        std::vector<int> freq(26, 0);
        for (char t : tasks) freq[t - 'A']++;

        std::priority_queue<int> maxHeap;
        for (int f : freq) if (f > 0) maxHeap.push(f);

        std::deque<std::pair<int,int>> cooldown; // {remaining, available_at}
        int time = 0;

        while (!maxHeap.empty() || !cooldown.empty()) {
            time++;
            if (!maxHeap.empty()) {
                int count = maxHeap.top() - 1;
                maxHeap.pop();
                if (count > 0) cooldown.push_back({count, time + n});
            }
            if (!cooldown.empty() && cooldown.front().second == time) {
                maxHeap.push(cooldown.front().first);
                cooldown.pop_front();
            }
        }
        return time;
    }
};

Complexity Analysis:

• Time Complexity: O(m log 26) = O(m). The heap has at most 26 distinct tasks.
• Space Complexity: O(26) = O(1).

Where it breaks: the cooldown check cooldown.peek()[1] == time must match exactly. Using <= instead of == can release tasks one step too early and produce incorrect results.

Common Mistakes

• Forgetting to handle n = 0. When n = 0, there’s no cooldown and the answer is just tasks.length. Both solutions handle this correctly since (maxFreq - 1) * (0 + 1) + countOfMax ≤ tasks.length always.
• Off-by-one in the cooldown timer. If a task runs at time t, it becomes available again at t + n + 1, not t + n.

Frequently Asked Questions

What does the formula (maxFreq - 1) * (n + 1) + countOfMax mean? Imagine maxFreq - 1 “frames” of size n + 1 (one slot for the most frequent task, n slots for other tasks or idle). The last partial frame holds countOfMax tasks (all tasks with maximum frequency).

When does idle time appear? When there aren’t enough distinct tasks to fill the cooldown gaps. If you only have one task type A repeated k times with cooldown n, you must insert n idle steps between each execution.

← All Problems