Time Complexity: The complexity is difficult to bound strictly but approaches $O(Total\_Intervals \times Unique\_Tasks)$. If the number of tasks is high and n is large, the simulation performs redundant checks for every time unit.

Why it fails: While this simulation can produce the correct answer, it is inefficient. It does not look ahead to optimize the arrangement globally. Instead, it makes local decisions that might result in a valid but non-minimal schedule. Furthermore, simulating the timeline creates unnecessary overhead when a mathematical calculation can derive the answer in linear time $O(N)$.

Core Insight for Task Scheduler

The key intuition for the LeetCode 621 solution is to recognize that the most frequent task acts as the bottleneck.

If the most frequent task A appears max_freq times, it requires max_freq - 1 cooling intervals between its executions. To minimize the total time, we should space out these As exactly n units apart. This creates max_freq - 1 groups (or chunks), where each group consists of one execution of A followed by n empty slots.

The final execution of A does not require a cooling period after it because the tasks are finished.

Visual Description: Imagine constructing a table where the number of rows equals max_freq.

1. We place the most frequent task in the first column of every row.
2. The first max_freq - 1 rows have a length of exactly n + 1 (1 task + n wait time).
3. The last row initially contains only the final execution of the most frequent task.
4. We then fill the empty slots (the n waiting periods) in the first max_freq - 1 rows with the remaining less frequent tasks.
5. If we have multiple tasks tied for the highest frequency, they extend the last row.

The invariant here is that if we can satisfy the spacing for the most frequent task, we can satisfy it for all less frequent tasks by simply filling the empty slots. If the empty slots are insufficient (i.e., we have too many tasks), we simply widen the schedule, which effectively means no idle time is needed.

Execution Flow

Let's trace the algorithm with tasks = ["A","A","A","B","B","B"], n = 2.

1. Count Frequencies:
   • A: 3
   • B: 3
2. Identify Max Frequency:
   • max_freq = 3 (from A).
3. Count Max-Frequency Tasks:
   • Both A and B have frequency 3.
   • num_max_tasks = 2.
4. Calculate Minimum Frame:
   • We consider the "full cycles" first. There are max_freq - 1 = 2 such cycles.
   • Each cycle length is n + 1 = 3.
   • Base calculation: 2 * 3 = 6. This accounts for A _ _ A _ _.
   • Add the tail: The last instances of A and B must be executed.
   • Total calculated: 6 + num_max_tasks = 6 + 2 = 8.
   • Visualizing the frame: A B _ A B _ A B.
5. Compare with Total Length:
   • tasks.length = 6.
   • Calculated = 8.
6. Result: max(8, 6) = 8.

Consider tasks = ["A","A","A","B","B","B"], n = 0.

1. max_freq = 3.
2. num_max_tasks = 2.
3. Calculation: (3 - 1) * (0 + 1) + 2 = 2 * 1 + 2 = 4.
4. tasks.length = 6.
5. Result: max(4, 6) = 6.

Proof of Correctness

The correctness relies on the Pigeonhole Principle and the greedy choice property.

The lower bound of the schedule is determined by the most frequent task. If task T appears k times, the schedule must span at least (k-1) * (n+1) + 1 slots to accommodate T. If multiple tasks share this max frequency, they simply append to the end of the sequence, increasing the "+1" term.

The formula (max_freq - 1) * (n + 1) + num_max_tasks strictly constructs a schedule with the minimum necessary idle slots to satisfy the bottleneck tasks.

If len(tasks) is greater than this calculated value, it means there are enough "other" tasks to fill all the idle slots generated by the bottleneck. We can insert these additional tasks into the gaps arbitrarily (or by widening the gaps beyond n). Since the constraint is a minimum gap of n, widening the gap is valid. Thus, if we have more tasks than the minimum frame, the answer is just the total number of tasks (zero idle time).

Reference Implementation

C++ Solution for LeetCode 621

cpp
#include <vector>
#include <algorithm>
#include <cmath>

class Solution {
public:
    int leastInterval(std::vector<char>& tasks, int n) {
        // Frequency array for A-Z
        std::vector<int> freqs(26, 0);
        for (char task : tasks) {
            freqs[task - 'A']++;
        }

        // Find the maximum frequency among all tasks
        int max_freq = 0;
        for (int f : freqs) {
            max_freq = std::max(max_freq, f);
        }

        // Count how many tasks have this max frequency
        int num_max_tasks = 0;
        for (int f : freqs) {
            if (f == max_freq) {
                num_max_tasks++;
            }
        }

        // Calculate the minimum length based on the most frequent task
        // (max_freq - 1) groups of size (n + 1), plus the final execution of max freq tasks
        int part_count = max_freq - 1;
        int part_length = n + 1;
        int min_length = part_count * part_length + num_max_tasks;

        // The answer is the max of the calculated frame or the actual number of tasks
        return std::max(min_length, (int)tasks.size());
    }
};

Java Solution for LeetCode 621

java
class Solution {
    public int leastInterval(char[] tasks, int n) {
        // Frequency array for A-Z
        int[] freqs = new int[26];
        for (char task : tasks) {
            freqs[task - 'A']++;
        }

        // Find the maximum frequency
        int maxFreq = 0;
        for (int f : freqs) {
            maxFreq = Math.max(maxFreq, f);
        }

        // Count how many tasks have that maximum frequency
        int numMaxTasks = 0;
        for (int f : freqs) {
            if (f == maxFreq) {
                numMaxTasks++;
            }
        }

        // Calculate theoretical minimum slots required
        // We have (maxFreq - 1) full cycles of length (n + 1)
        // Plus the tasks that need to be executed in the final cycle
        int minSlots = (maxFreq - 1) * (n + 1) + numMaxTasks;

        // Return the larger of the theoretical minimum or the raw task count
        return Math.max(minSlots, tasks.length);
    }
}

Python Solution for LeetCode 621

python
from collections import Counter

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        # Count frequencies of each task
        counts = Counter(tasks)
        
        # Find the maximum frequency
        max_freq = max(counts.values())
        
        # Count how many tasks have this max_freq
        num_max_tasks = sum(1 for count in counts.values() if count == max_freq)
        
        # Calculate the minimum intervals required by the bottleneck
        # (max_freq - 1) chunks of size (n + 1) + the final tasks
        part_count = max_freq - 1
        part_length = n + 1
        min_intervals = part_count * part_length + num_max_tasks
        
        # The result is constrained by the actual number of tasks if no idles are needed
        return max(min_intervals, len(tasks))