4.17.5 — Task Scheduler

LeetCode 621 · Medium

The problem

Each task takes one unit of time. The same task cannot run again until n units have passed. Different tasks have no restriction. The CPU may idle. Return the minimum total time to run everything.

tasks = ["A","A","A","B","B","B"], n = 2   →  8
    A B idle A B idle A B

tasks = ["A","A","A","B","B","B"], n = 0   →  6

The pattern

The greedy rule is: at every step, run the most frequent task that is currently allowed.

Why the most frequent? Because it is the one most likely to cause idling later. Spending its copies early spreads them out; leaving them until the end forces gaps you cannot fill.

That needs "the currently largest count", repeatedly, from a changing collection — which is a max-heap. Plus a queue holding tasks that are cooling down and cannot yet be chosen.

Solution 1 — simulation with a heap

Python

import heapq
from collections import Counter, deque

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)
        heap = [-c for c in counts.values()]        # max-heap by negation
        heapq.heapify(heap)

        cooling = deque()          # (remaining count, time it becomes available)
        time = 0

        while heap or cooling:
            time += 1

            if heap:
                remaining = heapq.heappop(heap) + 1     # one copy used (negated)
                if remaining:                            # still copies left
                    cooling.append((remaining, time + n))
            # else: the CPU idles this tick

            if cooling and cooling[0][1] == time:
                heapq.heappush(heap, cooling.popleft()[0])

        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 heap = new MaxHeap<number>();
  for (const c of counts.values()) heap.push(c);

  const cooling: Array<[number, number]> = [];
  let time = 0;

  while (heap.size || cooling.length) {
    time++;
    if (heap.size) {
      const remaining = heap.pop()! - 1;
      if (remaining > 0) cooling.push([remaining, time + n]);
    }
    if (cooling.length && cooling[0][1] === time) {
      heap.push(cooling.shift()![0]);
    }
  }

  return time;
}

The counts are negated, so heappop gives the largest and + 1 decrements it (adding 1 to a negative number moves it towards zero).

The queue is naturally ordered by availability time, because tasks enter it in increasing time order. So only the front ever needs checking — no second heap is required.

When the heap is empty but the queue is not, the CPU idles. The time += 1 happens unconditionally at the top, which is what counts the idle tick.

O(\text{total tasks} \times \log 26), effectively O(\text{total tasks}).

Solution 2 — the formula, O(n) with no heap

There is a closed form, and understanding it is worth more than the simulation.

Let maxCount be the highest frequency, and let numMax be how many different tasks share that frequency.

Build a skeleton out of the most frequent task. With maxCount = 3 and n = 2, task A forces this shape:

A _ _ A _ _ A

There are maxCount − 1 gaps, each of width n, plus the final A. So the skeleton takes:

(\text{maxCount} - 1) \times (n + 1) + 1

Now if several tasks tie for the highest frequency, each of them needs a slot in the final block too:

(\text{maxCount} - 1) \times (n + 1) + \text{numMax}

And then the catch. If there are plenty of other tasks, they fill every gap and the answer is simply len(tasks) — no idling at all. The formula can even come out smaller than the number of tasks in that case, which would be nonsense.

So take the larger of the two:

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)
        max_count = max(counts.values())
        num_max = sum(1 for c in counts.values() if c == max_count)

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

O(\text{total tasks}) time, O(1) space.

Checking it on the examples

["A","A","A","B","B","B"], n = 2. max_count = 3, num_max = 2 (both A and B).

Formula: (3−1) × (2+1) + 2 = 6 + 2 = 8. Task count is 6. Take the max → 8 ✓.

With n = 0: (3−1) × 1 + 2 = 4. Task count is 6. Take the max → 6 ✓. Here the len(tasks) term is what saves it, because with no cooldown there is never any idling.

Which to write

The formula is shorter and faster. The simulation is easier to trust and it generalises — if the problem later asks which task runs at each moment, or gives tasks different durations, the formula collapses and the heap still works.

Say the greedy rule, describe the simulation, then offer the formula with its derivation. That order shows you understand why the formula is true rather than having memorised it.

Where this goes next

• Reorganize String — rearrange a string so no two neighbours match. Same greedy rule with n = 1, and it is impossible exactly when maxCount > (len+1)/2, which is this formula in disguise.
• Rearrange String k Distance Apart — the same with a general gap.
• Real scheduling — rate limiting, retry backoff, and job schedulers all face "run the most urgent thing that is currently allowed". Chapter 11.18 builds a job scheduler properly.

What the interviewer will push on

"Why run the most frequent task first?" It is the one that will cause idling later, so its copies must be spread out early.

"Derive the formula." Skeleton of maxCount − 1 gaps of width n, plus the last block containing every task tied at the maximum.

"Why the max with len(tasks)?" When there are enough other tasks to fill every gap, there is no idling and the answer is just the task count.

"What if tasks had different durations?" The formula breaks; the heap simulation still works. This is the question that rewards having both.

One thing to volunteer: draw the skeleton A _ _ A _ _ A before writing the formula. Every term becomes visible from the picture, and it is far more convincing than the algebra alone.

Next: 4.17.6 Design Twitter — a heap doing a k-way merge inside a design problem.