6.4 Heap + Greedy Scheduling

Demo: Task Scheduler — LC 621 (Medium — Meta/Amazon High)

Statement (Demo): Given CPU tasks (letters) and a cooldown n, the same task must be at least n slots apart; idle slots are allowed. Return the minimum number of slots needed to run every task. Example: tasks=["A","A","A","B","B","B"], n=2 → 8 (A B idle A B idle A B) | ⚡ tasks.length ≤ 10⁴, 0 ≤ n ≤ 100

Approach: Greedy: in every cycle of n + 1 slots, run the tasks with the most remaining copies first. A max-heap of counts gives them in order; tasks that still have copies go back after the cycle. If the heap empties mid-cycle, the last cycle needs no idle padding. (MinHeap → 6.1.)

function leastInterval(tasks, n) {
  const counts = new Map();
  for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);
  const heap = new MinHeap((a, b) => b - a); // max-heap of remaining counts
  for (const c of counts.values()) heap.push(c);
  let time = 0;
  while (heap.size) {
    const waiting = [];
    let slots = 0;
    for (; slots <= n && heap.size; slots++) {
      const c = heap.pop(); // most copies left runs first
      if (c > 1) waiting.push(c - 1);
    }
    for (const c of waiting) heap.push(c);
    time += heap.size ? n + 1 : slots; // last cycle: no idle tail
  }
  return time;
}

Complexity: Time O(T log 26) ≈ O(T), Space O(26) (the counting formula (maxCount-1)*(n+1)+ties is O(T) — explain it as the follow-up)