621. Task Scheduler (Medium)

Problem

Given a list tasks (characters A-Z representing task types) and an integer n (the cooldown), return the least number of time units the CPU takes to finish. Between any two identical tasks, there must be at least n idle cycles.

Example

• tasks = ["A","A","A","B","B","B"], n = 2 → 8 (e.g., A B idle A B idle A B)
• tasks = ["A","A","A","B","B","B"], n = 0 → 6
• tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2 → 16

LeetCode 621 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, simulate cycle-by-cycle

Track remaining counts per task and the cooldown expiration for each. At each time step, pick any runnable task.

Python

from collections import Counter

def least_interval(tasks, n):
    counts = Counter(tasks)
    cooldown = {t: 0 for t in counts}
    time = 0
    while any(c > 0 for c in counts.values()):  # L1: T outer iterations
        picked = None
        best_count = 0
        for t, c in counts.items():              # L2: scan up to 26 tasks
            if c > 0 and cooldown[t] <= time and c > best_count:
                picked = t
                best_count = c
        if picked:
            counts[picked] -= 1                  # L3: O(1) decrement
            cooldown[picked] = time + n + 1      # L4: O(1) set cooldown
        time += 1
    return time

TypeScript

function leastInterval(tasks: string[], n: number): number {
    const counts = new Map<string, number>();
    for (const t of tasks) counts.set(t, (counts.get(t) ?? 0) + 1);
    const cooldown = new Map<string, number>();
    for (const t of counts.keys()) cooldown.set(t, 0);

    let time = 0;
    while ([...counts.values()].some(c => c > 0)) {  // L1: T outer iterations
        let picked: string | null = null;
        let bestCount = 0;
        for (const [t, c] of counts) {               // L2: scan up to 26 tasks
            if (c > 0 && (cooldown.get(t) ?? 0) <= time && c > bestCount) {
                picked = t; bestCount = c;
            }
        }
        if (picked) {
            counts.set(picked, counts.get(picked)! - 1);  // L3: O(1) decrement
            cooldown.set(picked, time + n + 1);            // L4: O(1) set cooldown
        }
        time++;
    }
    return time;
}

Go

func leastInterval(tasks []byte, n int) int {
    counts := make(map[byte]int)
    for _, t := range tasks { counts[t]++ }
    cooldown := make(map[byte]int)
    for t := range counts { cooldown[t] = 0 }

    time := 0
    for {
        anyLeft := false
        for _, c := range counts { if c > 0 { anyLeft = true; break } }
        if !anyLeft { break }
        var picked byte = 0; bestCount := 0 // L1: T outer iterations
        for t, c := range counts { // L2: scan up to 26 tasks
            if c > 0 && cooldown[t] <= time && c > bestCount { picked = t; bestCount = c }
        }
        if bestCount > 0 {
            counts[picked]--              // L3: O(1) decrement
            cooldown[picked] = time + n + 1 // L4: O(1) set cooldown
        }
        time++
    }
    return time
}

Swift

final class Solution {
    func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
        var remaining = Dictionary(tasks.map { ($0, 1) }, uniquingKeysWith: +)
        var availableAt: [Character: Int] = [:]
        var time = 0
        while !remaining.isEmpty { let ready = remaining.keys.filter { availableAt[$0, default: 0] <= time }.max { remaining[$0]! < remaining[$1]! }; if let task = ready { remaining[task]! -= 1; if remaining[task] == 0 { remaining.removeValue(forKey: task) }; availableAt[task] = time + n + 1 }; time += 1 }
        return time
    }
}

Where the time goes, line by line

Variables: T = total time units in the answer, t = number of distinct task types (at most 26).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$	T	$O(T)$
L2 (scan tasks)	$O(t)$	T	$O(T · t)$ ← dominates
L3-L4 (update)	$O(1)$	up to T	$O(T)$

At each time step we scan all task types (at most 26). Since t is bounded by 26, $O(T · 26)$ = $O(T)$.

Complexity

• Time: $O(T · t)$ = $O(T)$ since t ≤ 26. Correct but slow on large T (L2 scan).
• Space: $O(t)$ = $O(26)$.

Choosing highest-remaining-count is key, otherwise you strand long runs.

Approach 2: Max-heap + cooldown queue

Max-heap of remaining counts; after running a task, enqueue it with its ready-time into a FIFO. Each cycle: move expired tasks from the queue back into the heap, then run the heap’s top.

Python

import heapq
from collections import Counter, deque

def least_interval(tasks, n):
    heap = [-c for c in Counter(tasks).values()]
    heapq.heapify(heap)                          # L1: O(t) heapify
    cooldown = deque()   # (ready_time, negated_count_remaining)
    time = 0
    while heap or cooldown:                       # L2: T iterations total
        time += 1
        if heap:
            c = heapq.heappop(heap) + 1          # L3: O(log t) pop
            if c < 0:
                cooldown.append((time + n, c))   # L4: O(1) enqueue
        if cooldown and cooldown[0][0] == time:
            _, c = cooldown.popleft()
            heapq.heappush(heap, c)              # L5: O(log t) push
    return time

TypeScript

class MaxHeap {
    private data: number[] = [];
    get size(): number { return this.data.length; }
    push(val: number): void {
        this.data.push(val);
        this._siftUp(this.data.length - 1);
    }
    pop(): number {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) { this.data[0] = last; this._siftDown(0); }
        return top;
    }
    private _siftUp(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p] >= this.data[i]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p;
        }
    }
    private _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let largest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l] > this.data[largest]) largest = l;
            if (r < n && this.data[r] > this.data[largest]) largest = r;
            if (largest === i) break;
            [this.data[largest], this.data[i]] = [this.data[i], this.data[largest]]; i = largest;
        }
    }
}

function leastInterval(tasks: string[], n: number): number {
    const freq = new Map<string, number>();
    for (const t of tasks) freq.set(t, (freq.get(t) ?? 0) + 1);

    const heap = new MaxHeap();
    for (const c of freq.values()) heap.push(c);  // L1: O(t) build heap

    // cooldown queue: [readyTime, remainingCount]
    const cooldown: Array<[number, number]> = [];
    let time = 0;

    while (heap.size > 0 || cooldown.length > 0) {  // L2: T iterations
        time++;
        if (heap.size > 0) {
            const c = heap.pop() - 1;               // L3: O(log t) pop
            if (c > 0)
                cooldown.push([time + n, c]);        // L4: O(1) enqueue
        }
        if (cooldown.length > 0 && cooldown[0][0] === time) {
            const [, c] = cooldown.shift()!;
            heap.push(c);                            // L5: O(log t) push
        }
    }
    return time;
}

Go

package main

import (
    "container/heap"
    "fmt"
)

type MaxHeap []int
func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}

func leastInterval(tasks []byte, n int) int {
    freq := make(map[byte]int)
    for _, t := range tasks { freq[t]++ }
    h := &MaxHeap{}
    heap.Init(h)
    for _, c := range freq { heap.Push(h, c) } // L1: O(t) build heap
    type item struct{ readyTime, count int }
    cooldown := []item{}
    time := 0
    for h.Len() > 0 || len(cooldown) > 0 { // L2: T iterations total
        time++
        if h.Len() > 0 {
            c := heap.Pop(h).(int) - 1 // L3: O(log t) pop
            if c > 0 { cooldown = append(cooldown, item{time + n, c}) } // L4: O(1)
        }
        if len(cooldown) > 0 && cooldown[0].readyTime == time {
            heap.Push(h, cooldown[0].count) // L5: O(log t) push
            cooldown = cooldown[1:]
        }
    }
    return time
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    assert(leastInterval([]byte{'A','A','A','B','B','B'}, 2) == 8)
    assert(leastInterval([]byte{'A','A','A','B','B','B'}, 0) == 6)
    assert(leastInterval([]byte{'A','A','A','A','A','A','B','C','D','E','F','G'}, 2) == 16)
    assert(leastInterval([]byte{'A','B','C','D','A','B','C','D'}, 2) == 8)
    assert(leastInterval([]byte{'A','A','A'}, 3) == 9)
    assert(leastInterval([]byte{'A','A','A'}, 0) == 3)
    fmt.Println("all tests pass")
}

func main() { runTests() }

Swift

private struct CoolingTask { let ready: Int; let count: Int }
final class Solution {
    func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
        let counts = Dictionary(tasks.map { ($0, 1) }, uniquingKeysWith: +)
        var heap = BinaryHeap<Int>(hasHigherPriority: >)
        for count in counts.values { heap.insert(count) }
        var cooling: [CoolingTask] = []
        var time = 0
        while !heap.isEmpty || !cooling.isEmpty { time += 1; if let count = heap.removeRoot(), count > 1 { cooling.append(CoolingTask(ready: time + n, count: count - 1)) }; if cooling.first?.ready == time { heap.insert(cooling.removeFirst().count) } }
        return time
    }
}

Where the time goes, line by line

Variables: T = total time units in the answer, t = number of distinct task types (at most 26).

Line	Per-call cost	Times executed	Contribution
L1 (heapify)	$O(t)$	1	$O(t)$
L2 (outer loop)	$O(1)$	T	$O(T)$
L3 (heappop)	$O(log t)$	up to T	$O(T log t)$ ← dominates
L4 (enqueue)	$O(1)$	up to T	$O(T)$
L5 (heappush)	$O(log t)$	up to T	$O(T log t)$

Since t ≤ 26, $O(T log t)$ = $O(T log 26)$ = $O(T)$.

Complexity

• Time: $O(T log t)$ = $O(T)$ since t ≤ 26 (L3/L5 dominate).
• Space: $O(t)$ = $O(26)$.

Cleaner than the brute force; a natural fit for “greedy scheduling with recurring cooldowns.”

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Closed-form math (optimal)

Let max_count be the count of the most-frequent task and ties be the number of tasks that hit max_count. The answer is:

max(len(tasks), (max_count - 1) * (n + 1) + ties)

Intuition: build a skeleton of max_count - 1 “rows” of width n + 1, plus a tail row with ties slots. Other tasks slot into the idle spaces. If there are more tasks than that schedule provides for, the total time is just len(tasks) (no idle needed).

Python

from collections import Counter

def least_interval(tasks, n):
    counts = Counter(tasks)                              # L1: O(T) build counter
    max_count = max(counts.values())                     # L2: O(t) find max
    ties = sum(1 for c in counts.values() if c == max_count)  # L3: O(t) count ties
    return max(len(tasks), (max_count - 1) * (n + 1) + ties)  # L4: O(1) formula

TypeScript

function leastInterval(tasks: string[], n: number): number {
    const freq = new Map<string, number>();
    for (const t of tasks) freq.set(t, (freq.get(t) ?? 0) + 1);  // L1: O(T) build counter

    let maxCount = 0;
    for (const c of freq.values()) if (c > maxCount) maxCount = c;  // L2: O(t) find max

    let ties = 0;
    for (const c of freq.values()) if (c === maxCount) ties++;       // L3: O(t) count ties

    return Math.max(tasks.length, (maxCount - 1) * (n + 1) + ties); // L4: O(1) formula
}

Go

package main

import "fmt"

func leastInterval(tasks []byte, n int) int {
    freq := make(map[byte]int)
    for _, t := range tasks { freq[t]++ } // L1: O(T) build counter
    maxCount := 0
    for _, c := range freq { if c > maxCount { maxCount = c } } // L2: O(t)
    ties := 0
    for _, c := range freq { if c == maxCount { ties++ } } // L3: O(t)
    result := (maxCount-1)*(n+1) + ties // L4: O(1) formula
    if len(tasks) > result { return len(tasks) }
    return result
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    assert(leastInterval([]byte{'A','A','A','B','B','B'}, 2) == 8)
    assert(leastInterval([]byte{'A','A','A','B','B','B'}, 0) == 6)
    assert(leastInterval([]byte{'A','A','A','A','A','A','B','C','D','E','F','G'}, 2) == 16)
    assert(leastInterval([]byte{'A','B','C','D','A','B','C','D'}, 2) == 8)
    assert(leastInterval([]byte{'A','A','A'}, 3) == 9)
    assert(leastInterval([]byte{'A','A','A'}, 0) == 3)
    fmt.Println("all tests pass")
}

func main() { runTests() }

Swift

final class Solution {
    func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
        let counts = Dictionary(tasks.map { ($0, 1) }, uniquingKeysWith: +).values
        let maximum = counts.max()!
        let tied = counts.filter { $0 == maximum }.count
        return max(tasks.count, (maximum - 1) * (n + 1) + tied)
    }
}

Where the time goes, line by line

Variables: T = len(tasks) (total tasks), t = number of distinct task types (at most 26).

Line	Per-call cost	Times executed	Contribution
L1 (Counter / freq build)	$O(T)$	1	$O(T)$ ← dominates
L2 (max)	$O(t)$	1	$O(t)$
L3 (count ties)	$O(t)$	1	$O(t)$
L4 (formula)	$O(1)$	1	$O(1)$

Building the Counter at L1 touches every task once. The remaining steps scan at most 26 entries. The formula at L4 is a single expression: no simulation, no heap.

Complexity

• Time: $O(T)$ where T = len(tasks), driven by L1 (Counter construction).
• Space: $O(t)$ = $O(26)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_621.py and run.
# Uses the closed-form math approach (Approach 3).
from collections import Counter

def least_interval(tasks, n):
    counts = Counter(tasks)
    max_count = max(counts.values())
    ties = sum(1 for c in counts.values() if c == max_count)
    return max(len(tasks), (max_count - 1) * (n + 1) + ties)

def _run_tests():
    # Examples from problem statement
    assert least_interval(["A","A","A","B","B","B"], 2) == 8
    assert least_interval(["A","A","A","B","B","B"], 0) == 6
    assert least_interval(["A","A","A","A","A","A","B","C","D","E","F","G"], 2) == 16
    # No idle needed: enough variety to fill cooldown
    assert least_interval(["A","B","C","D","A","B","C","D"], 2) == 8
    # Single task type
    assert least_interval(["A","A","A"], 3) == 9   # A _ _ _ A _ _ _ A
    # n=0: no cooldown, answer = len(tasks)
    assert least_interval(["A","A","A"], 0) == 3
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

// Uses the closed-form math approach (Approach 3).
// See 621-task-scheduler-approach3.ts for the full implementation.
console.assert(leastInterval(['A','A','A','B','B','B'], 2) === 8);
console.assert(leastInterval(['A','A','A','B','B','B'], 0) === 6);
console.assert(leastInterval(['A','A','A','A','A','A','B','C','D','E','F','G'], 2) === 16);
console.assert(leastInterval(['A','B','C','D','A','B','C','D'], 2) === 8);
console.assert(leastInterval(['A','A','A'], 3) === 9);
console.assert(leastInterval(['A','A','A'], 0) === 3);
console.log("all tests pass");

Summary

Approach	Time	Space	Notes
Simulation	$O(T · 26)$	$O(26)$	Direct; slow on large T
Max-heap + cooldown queue	$O(T)$	$O(26)$	Generalizes to heterogeneous cooldowns
Closed-form math	$O(T)$	$O(26)$	Tightest for this specific problem

The closed-form is fast and exact; the heap variant is what you reach for when cooldowns vary per task or priorities change dynamically.

Related data structures

• Heaps / Priority Queues, max-heap + waiting queue for cooldown scheduling
• Queues, cooldown FIFO
• Hash Tables, frequency counts

Related concepts

• Heap and Priority Queue, the priority frontier for repeatedly taking the smallest, largest, or most urgent item.
• Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.