621. Task Scheduler

Quick Identifier

• Topic: heap-priority-queue
• Pattern: Top-K / Heap (simulation) + greedy layout
• Difficulty: Medium
• Companies: Amazon, Microsoft, Google, Meta, Bloomberg
• Frequency: High
• LeetCode: 621

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(1) for fixed uppercase alphabet from the optimal approach.
• Core Mechanism: Given tasks A..Z, each takes one time slot; the same task needs at least n idle/other-task slots between repeats. Return the minimum clock length to finish all tasks.

Concept Explanation

Given tasks A..Z, each takes one time slot; the same task needs at least n idle/other-task slots between repeats. Return the minimum clock length to finish all tasks.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• Cooldown n between identical labels
• Maximize utilization by spreading most frequent task
• Answer is max(|tasks|, (maxFreq-1)*(n+1) + numWithMaxFreq) or heap simulation

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Simulation — max-heap of counts, each cycle pick best available, cooldown queue — models process — O(total time) with heap log 26.
• Math — arrange (maxFreq-1) blocks of length (n+1) then append tail of max-frequency symbols — O(26) time, O(1) space — preferred when explained.

Optimal Solution

Go

func leastInterval(tasks []byte, cooldown int) int {
	counts := make([]int, 26)
	for _, task := range tasks {
		counts[task-'A']++
	}
	maxFreq := 0
	for _, count := range counts {
		if count > maxFreq {
			maxFreq = count
		}
	}
	numWithMaxFreq := 0
	for _, count := range counts {
		if count == maxFreq {
			numWithMaxFreq++
		}
	}
	block := (maxFreq-1)*(cooldown+1) + numWithMaxFreq
	if len(tasks) > block {
		return len(tasks)
	}
	return block
}

JavaScript

function leastInterval(tasks, cooldown) {
  const freq = new Map();
  for (const label of tasks) {
    freq.set(label, (freq.get(label) ?? 0) + 1);
  }
  let maxFreq = 0;
  for (const count of freq.values()) {
    maxFreq = Math.max(maxFreq, count);
  }
  let numWithMaxFreq = 0;
  for (const count of freq.values()) {
    if (count === maxFreq) {
      numWithMaxFreq += 1;
    }
  }
  const minSlots = (maxFreq - 1) * (cooldown + 1) + numWithMaxFreq;
  return Math.max(tasks.length, minSlots);
}

Walkthrough

tasks = ["A","A","A","B","B","B"], n = 2. Frequencies: A=3, B=3, maxFreq=3, numWithMaxFreq=2.

Blocks for top letter: (3-1)*(2+1) + 2 = 8. Total tasks 6 → answer max(6,8)=8.

Layout intuition: A ? ? A ? ? A with B filling blanks: A B idle A B idle A B.

Invariant: The formula counts slots forced by the most frequent letter(s); if extra tasks fill idle time, length drops to len(tasks).

Edge Cases

• n = 0 — sum of counts only (no gap rule)
• Single task type — large idle spacing
• Many distinct tasks — often answer = len(tasks)

Pitfalls

• Off-by-one on (n+1) block width (task plus n gaps)
• Forgetting max(len(tasks), formula) when leftovers saturate idles

Similar Problems

• 1046. Last Stone Weight — heap simulation / greedy by largest item
• 1834. Single-Threaded CPU — CPU scheduling with priority timing

Variants

• Heap simulation returns same count — useful if constraints generalized beyond 26 letters
• Weighted task lengths — no longer LeetCode 621 classical form

Mind-Map Tags

#greedy #cooldown #frequency #math #heap-alternative