Task Scheduler: the idle-time problem and when a formula beats a heap

The problem (LeetCode 621): you have a list of CPU tasks, each identified by a letter A–Z, and a cooldown value n. A CPU can execute one task per interval, or stay idle. The same task cannot be repeated until at least n intervals have passed since its last execution. Find the minimum total intervals to finish everything.

Example: tasks = ["A","A","A","B","B","B"], n = 2. One valid schedule is A -> B -> idle -> A -> B -> idle -> A -> B — 8 intervals total.

The cooldown constraint makes this non-trivial. Without it, the answer is just len(tasks). With it, idle slots can appear — and the question is whether idle is actually necessary and, if so, how much.

What the constraints force

1 <= tasks.length <= 10^4. Up to ten thousand tasks. That's small enough to simulate step by step, but O(m * log k) where m is the total intervals (which can exceed tasks.length when idle slots appear) is the cost you pay for simulation. At the extreme — one task type repeated 10,000 times with n = 100 — the total intervals balloon to roughly 1,000,000. Still fast enough, but the math formula skips all of that.

tasks[i] is an uppercase English letter. At most 26 distinct task types. This is the constraint that makes everything tractable. The heap never has more than 26 entries. Frequency counting fits in a fixed-size array. The formula's max_count is bounded by 26.

0 <= n <= 100. When n = 0, there's no cooldown at all and you simply run every task back to back — answer is len(tasks). When n = 100, you might need 100 idle slots between each pair of identical high-frequency tasks. Both extremes are handled cleanly by both approaches.

Approach 1: Heap simulation

The direct approach simulates the CPU clock tick by tick. At each tick, you want the highest-frequency eligible task — so a max-heap ordered by remaining count is the natural data structure. Tasks that are cooling down wait in a queue; once their cooldown expires, they re-enter the heap.

Python uses a min-heap, so I negate all counts to fake a max-heap. That freq += 1 on line 135 of the source confused me the first time I read it — you're adding 1 to a negative number, effectively decrementing the absolute count by 1.

import heapq
from collections import Counter, deque
from typing import List
 
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        max_heap = [-freq for freq in count.values()]
        heapq.heapify(max_heap)
 
        # Each entry in waiting_queue: (negated_freq, time_when_eligible)
        waiting_queue = deque()
        time = 0
 
        while max_heap or waiting_queue:
            time += 1
 
            # Release any task whose cooldown just ended
            if waiting_queue and waiting_queue[0][1] == time:
                freq = waiting_queue.popleft()[0]
                heapq.heappush(max_heap, freq)
 
            if max_heap:
                freq = heapq.heappop(max_heap)
                freq += 1  # decrement abs count (freq is negative)
                if freq < 0:
                    # Still has remaining occurrences; cool it down
                    waiting_queue.append((freq, time + n + 1))
 
        return time

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        var count = new Dictionary<char, int>();
        foreach (char task in tasks)
            count[task] = count.GetValueOrDefault(task, 0) + 1;
 
        // .NET PriorityQueue is a min-heap; use negative priority for max
        var maxHeap = new PriorityQueue<int, int>();
        foreach (int freq in count.Values)
            maxHeap.Enqueue(freq, -freq);
 
        var waitingQueue = new Queue<(int freq, int availableTime)>();
        int time = 0;
 
        while (maxHeap.Count > 0 || waitingQueue.Count > 0) {
            time++;
 
            if (waitingQueue.Count > 0 && waitingQueue.Peek().availableTime == time) {
                var (freq, _) = waitingQueue.Dequeue();
                maxHeap.Enqueue(freq, -freq);
            }
 
            if (maxHeap.Count > 0) {
                int freq = maxHeap.Dequeue() - 1;
                if (freq > 0)
                    waitingQueue.Enqueue((freq, time + n + 1));
            }
        }
 
        return time;
    }
}

Tracing the first example step by step

tasks = ["A","A","A","B","B","B"], n = 2. After counting: A:3, B:3. Heap contains [-3, -3] (two entries, both with count 3).

Output: 8. Matches the expected answer.

The idle slots at t=3 and t=6 happen because all tasks are in cooldown simultaneously. There's simply nothing to run.

Complexity

Time: O(m * log k) where m is the total intervals output and k is the number of distinct task types (at most 26). Each interval does at most one heap push and one heap pop, each costing O(log k). In the worst case m is much larger than len(tasks) — think single task type with high n.

Space: O(k) — the heap and the waiting queue together hold at most k entries, one per distinct task type.

Approach 2: the mathematical formula

The simulation is correct but does more work than necessary. You don't actually need to know which task runs at which tick — just the count.

The insight comes from the most-frequent task. Call its count max_freq. That task forces a certain number of mandatory gaps: between each pair of consecutive executions, you need at least n intervals. With max_freq occurrences, there are max_freq - 1 gaps, each of size at least n. That minimum structure looks like this:

[chunk][gap][chunk][gap]...[chunk][gap][last_chunk]
 (n+1)       (n+1)          (n+1)      (max_count)

Each full chunk has size n + 1 — one slot for the max-frequency task plus n slots for either other tasks or idle. There are max_freq - 1 such full chunks. The final chunk has only the tasks that share max_freq — call that count max_count. Nothing after the last execution needs a cooldown.

The formula: (max_freq - 1) * (n + 1) + max_count.

But this can undercount. If there are enough distinct tasks or enough total volume that they fill every gap and overflow into more intervals, the answer is just len(tasks). Hence: max((max_freq - 1) * (n + 1) + max_count, len(tasks)).

from collections import Counter
from typing import List
 
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        max_freq = max(count.values())
        max_count = sum(1 for freq in count.values() if freq == max_freq)
 
        formula_result = (max_freq - 1) * (n + 1) + max_count
        return max(formula_result, len(tasks))

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        var count = new Dictionary<char, int>();
        foreach (char task in tasks)
            count[task] = count.GetValueOrDefault(task, 0) + 1;
 
        int maxFreq = count.Values.Max();
        int maxCount = count.Values.Count(freq => freq == maxFreq);
 
        int formulaResult = (maxFreq - 1) * (n + 1) + maxCount;
        return Math.Max(formulaResult, tasks.Length);
    }
}

Tracing example 1 with the formula

tasks = ["A","A","A","B","B","B"], n = 2. Count: A:3, B:3. max_freq = 3, max_count = 2.

(3 - 1) * (2 + 1) + 2 = 2 * 3 + 2 = 8
max(8, 6) = 8

The scheduled structure looks like:

chunk 1: A  B  _
chunk 2: A  B  _
last:    A  B

Three full columns, 8 slots total. Matches.

Tracing example 2

tasks = ["A","C","A","B","D","B"], n = 1. Count: A:2, B:2, C:1, D:1. max_freq = 2, max_count = 2.

(2 - 1) * (1 + 1) + 2 = 1 * 2 + 2 = 4
max(4, 6) = 6

Here len(tasks) = 6 wins. The schedule is A -> B -> C -> D -> A -> B — no idle needed because the task variety is high enough to fill the gaps organically. This is the case the formula can't describe structurally (the chunk picture breaks down), but the max(formula, len(tasks)) bound catches it exactly.

Tracing example 3

tasks = ["A","A","A","B","B","B"], n = 3. Count: A:3, B:3. max_freq = 3, max_count = 2.

(3 - 1) * (3 + 1) + 2 = 2 * 4 + 2 = 10
max(10, 6) = 10

The structure:

chunk 1: A  B  _  _
chunk 2: A  B  _  _
last:    A  B

10 slots. Two idle slots per chunk because only two tasks exist but cooldown is 3.

Complexity

Time: O(k) where k <= 26 — one pass over the frequency map. Effectively O(1) since k is bounded. The Counter construction itself is O(N) in the number of tasks, which dominates.

Space: O(k) for the frequency map.

Edge cases that actually matter

n = 0, no cooldown. Both approaches handle this, but via different paths. The formula gives (max_freq - 1) * 1 + max_count, and since len(tasks) >= max_freq, the max always returns len(tasks). In simulation, the waiting queue never blocks anything because time + 0 + 1 = time + 1 — tasks re-enter the heap on the very next tick and there's always something to run.

Single task type. tasks = ["A","A","A","A"], n = 2. max_freq = 4, max_count = 1. Formula: 3 * 3 + 1 = 10. The schedule is A _ _ A _ _ A _ _ A — all idle. The formula captures this cleanly because the chunk structure is obvious.

All tasks identical frequency. tasks = ["A","B","C","D"], n = 2. Every frequency is 1. max_freq = 1, max_count = 4. Formula: 0 * 3 + 4 = 4. max(4, 4) = 4. No idle needed; one pass through all tasks in any order.

max_count ties at high frequency. If several task types share max_freq, the last chunk fills with all of them, and the formula accounts for this via max_count. The simulation handles it naturally — the heap just has multiple equally-ranked candidates and picks any (doesn't matter which).

High-frequency single task with large n. tasks = ["A"] * 10000, n = 100. Formula: 9999 * 101 + 1 = 1,009,900 total intervals. Simulation would loop nearly 1 million times. This is where the O(1) formula is dramatically better — not 10x, but orders of magnitude.

Comparison

k <= 26 so log k is effectively constant. The real cost difference is m vs N. When the schedule has no idle time, m = N and both approaches are within a constant of each other. When idle time is large, m >> N and the formula wins decisively.

The underlying pattern: greedy frequency scheduling

This problem is the canonical instance of a family of scheduling problems where the constraint is "minimum gap between repeats of the same item." The structure in all of them is the same: the most-frequent item is the bottleneck, and everything else either fills the gaps or creates more idle time.

The pattern appears in several places in competitive programming:

• 767. Reorganize String — cooldown of 1 (no two adjacent identical characters). The formula simplifies: if max_freq > (len(s) + 1) / 2, it's impossible. Otherwise the chunk structure guarantees a valid arrangement. No idle; rearrangement within the original length.
• 358. Rearrange String k Distance Apart — direct generalization: cooldown is k. Same chunk logic; now returns "" instead of idle count if impossible.
• 1054. Distant Barcodes — barcodes must not have identical neighbors. Equivalent to Reorganize String with a different output type. The same "fill the even indices first with the most-frequent element" insight applies.
• 2365. Task Scheduler II — each task has its own individual cooldown (a map, not a single n). Simulation with a map-based cooldown tracker replaces the uniform queue.

In all of them, the core observation is: count frequencies, find the bottleneck (the maximum frequency), build around it. The formula approach works when there's a closed-form structure; simulation is the fallback when individual task cooldowns vary.

I'd ship the formula version — it's five lines, O(N), and the logic is self-documenting once you draw the chunk picture. The heap simulation is the one I'd reach for in an interview if I blanked on the formula derivation, or in problems where the cooldown varies per task type. Both are worth knowing because they represent different levels of insight into the same problem.

The heap series so far has covered k-th element extraction (Kth Largest), top-k selection (Top K Frequent Elements), k-way merge (Merge K Sorted Lists), and now scheduled access (Task Scheduler). The next natural step is the running-median problem — two heaps, one max and one min, that maintain the split point as elements stream in. That's where the heap data structure shows what it's really for.