Frontend Beauty
ESC

Type to search the knowledge base.

Task Scheduler

Min time to run tasks with cooldown n — formula from max frequency, or simulate with a max-heap.

intermediate3 min read
  • dsa
  • heap
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

CPU tasks labeled by letters. Same letter needs n units of cooldown between runs (other tasks or idle can fill). Each task takes 1 unit. Return minimum units of time to finish all tasks.

Input:  tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
// A B idle A B idle A B

Brute force: simulation

Always schedule the available task with highest remaining count (greedy). Use a max-heap + cooldown queue. Correct and interview-friendly.

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

  // max-heap via sorted array of counts
  let heap = [...freq.values()].sort((a, b) => b - a);
  let time = 0;

  while (heap.length) {
    const next: number[] = [];
    let slots = n + 1; // one frame of n+1 slots
    while (slots > 0 && heap.length) {
      const cnt = heap.shift()!;
      if (cnt - 1 > 0) next.push(cnt - 1);
      time++;
      slots--;
    }
    heap.push(...next);
    heap.sort((a, b) => b - a);
    if (heap.length) time += slots; // remaining idles in this frame
  }
  return time;
}
Time O(t · Σ log Σ) with proper heap; small alphabet here
Space O(Σ)

Optimal math formula

Let maxf be the highest frequency. Let extra be how many tasks share that frequency.

You need at least (maxf - 1) * (n + 1) + extra slots to place the most frequent tasks with gaps. Also need at least tasks.length (no idle if diverse enough).

function leastInterval(tasks: string[], n: number): number {
  const freq = Array(26).fill(0);
  for (const t of tasks) freq[t.charCodeAt(0) - 65]++;

  let maxf = 0;
  for (const f of freq) maxf = Math.max(maxf, f);

  let extra = 0;
  for (const f of freq) if (f === maxf) extra++;

  const framed = (maxf - 1) * (n + 1) + extra;
  return Math.max(tasks.length, framed);
}
Time O(t)
Space O(1) for 26 letters

Walk A×3, B×3, n=2

maxf=3, extra=2 → (3-1)*(3)+2 = 8. Length=6 → answer 8.

Edge cases

  • n = 0 → tasks.length
  • All unique tasks → length
  • One task repeated many times → pure idles
  • Many tasks fill all idle slots

Common bugs

  • Forgetting Math.max with tasks.length
  • Off-by-one on (maxf - 1) * (n + 1)
  • Counting extra wrong when multiple peak frequencies

Interview delivery

  1. Cooldown between same labels.
  2. Give formula + justify.
  3. Optional heap simulation.
  4. Complexity.
  5. Trace classic A/B example.

Further reading