LeetCode 621 · Heap / Priority Queue

Task Scheduler, explained with a picture

A chef whose stations need time to cool down.

MediumHeap / Priority Queue
▶ Watch it step by step

The problem

A CPU must run a list of tasks (letters). Each takes one time unit. The same task must wait at least n units before running again; the CPU can sit idle. Find the fewest time units to finish all tasks.

Input:  tasks = "AAABBB", n = 2
Output: 8   (A B idle A B idle A B)

Picture it

Picture a chef cooking dishes at stations that need n minutes to cool down after use. Each minute, the chef cooks the dish with the most portions left that is ready (a max-heap picks it). A cooked dish rests in a cooling queue until it may be used again. If nothing is ready, the chef waits (an idle minute).

How to recognise it

  • You are scheduling items one per time step, and the same kind of item must wait a minimum gap before it may run again.
  • You want the fewest total steps, and idle steps are allowed.
  • A greedy rule suggests itself: run the kind with the most work left that is currently allowed.
  • Counts change after every step, and you repeatedly need the largest available count. That is a job for a heap (a tree stored in a list that hands out its best item in O(log n)), together with a waiting area for items that are cooling down.
  • Up to 10^4 tasks and a cooldown up to 100: the answer can be over a million time units, so enumerating schedules is out.

Start with brute force

Try every possible schedule: at each time unit, either idle or run any kind of task that is ready, and keep the shortest schedule that finishes everything.

from collections import Counter

def least_interval_brute(tasks, n):
    kinds = sorted(Counter(tasks).items())
    start = (tuple(c for _, c in kinds), tuple(0 for _ in kinds))
    seen, frontier, t = {start}, [start], 0
    while frontier:
        nxt = []
        for left, wait in frontier:
            if sum(left) == 0:
                return t
            tick = tuple(max(0, w - 1) for w in wait)
            options = [(left, tick)]                  # stay idle
            for i, c in enumerate(left):
                if c and wait[i] == 0:                # this kind is ready now
                    l2, w2 = list(left), list(tick)
                    l2[i] -= 1
                    w2[i] = n
                    options.append((tuple(l2), tuple(w2)))
            for o in options:
                if o not in seen:
                    seen.add(o)
                    nxt.append(o)
        frontier, t = nxt, t + 1
    return 0

This breadth-first search over states (counts left, cooldown per kind) is correct, but the number of states grows exponentially with the counts. With 10^4 tasks it is hopeless.

From brute force to the idea

  1. Find the waste. Most branches are clearly worse: if a task of the most frequent kind is ready, running something rarer first only delays the bottleneck.
  2. Go greedy. Each time unit, run the ready kind with the most copies left. Keep counts negated in a heap so Python's min-heap acts as a max-heap.
  3. Park cooling tasks. After running a kind, if copies remain, put (count left, time + n) in a queue. The time + n value is when it becomes ready: it ran at time, so units time + 1 to time + n are the gap.
  4. Release in order. One task runs per unit, so ready times in the queue are increasing; only its front needs checking. At the end of unit time, if the front is ready, push it back into the heap.
  5. Idle units happen by themselves. If the heap is empty but the queue is not, time still advances, which is the idle unit.

This is the key idea: a max-heap of ready counts plus a cooldown queue simulates the greedy schedule.

The key idea

Greedy: always run the most frequent available task; a queue holds tasks in cooldown. (Formula version: (maxCount − 1) × (n + 1) + number of tasks with maxCount.)

Python solution

def least_interval(tasks, n):
    heap = [-c for c in Counter(tasks).values()]
    heapify(heap)
    cooling, time = deque(), 0         # (count left, ready time)
    while heap or cooling:
        time += 1
        if heap:
            c = heappop(heap) + 1           # do the most-needed task
            if c: cooling.append((c, time + n))
        if cooling and cooling[0][1] == time:
            heappush(heap, cooling.popleft()[0])
    return time

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter, deque from heapq import heappush, heappop, heapify

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (search all schedules)Exponential in the number of tasksExponential: every distinct state is stored
Heap and queue (shown code)O(T log 26), where T is the answer; at most 26 kinds, so each heap step is tiny. T is at most about (count of the commonest task) × (n + 1)O(1): at most 26 entries in total

Edge cases

  • n = 0 (AAABBB): returns 6, with no idle units.
  • All tasks distinct (ABC, n = 5): returns 3; nothing ever has to wait.
  • One kind (AAA, n = 2): returns 7 (A, idle, idle, A, idle, idle, A).
  • Empty list: returns 0.
  • Example (AAABBB, n = 2): returns 8.
  • Largest input: 10^4 copies of A with n = 100 gives 1,009,900 loop iterations, still fast.
  • Imports: needs heapify, heappop, heappush, Counter and deque; the snippet omits them. The input is a list of letters.

Common mistakes

  • Waiting n + 1 units after the run instead of n, so tasks cool for one unit too long. AAABBB with n = 2 then returns 10.
  • Running the least frequent kind first, which leaves the bottleneck for the end.
  • Computing only (max_count - 1) * (n + 1) and forgetting the tail: every kind tied for the highest count adds one more unit.
  • Forgetting that the answer can never be below the number of tasks.
Your turn: no heap needed

Compute the same answer in O(n) with no heap and no simulation. Describe your approach, then write it if you like.

Compare with our answer

The commonest kind (count m) forces a skeleton of m - 1 full blocks of n + 1 units, followed by a last row that holds one copy of every kind tied for count m. Other tasks fit into the idle slots. If there are so many tasks that no idle slots remain, the answer is just the number of tasks.

from collections import Counter

def least_interval_formula(tasks, n):
    counts = Counter(tasks)
    m = max(counts.values(), default=0)
    tied = sum(1 for c in counts.values() if c == m)
    return max(len(tasks), (m - 1) * (n + 1) + tied)

For AAABBB with n = 2 it gives max(6, 2 × 3 + 2) = 8. Time O(n) to count, space O(1).

A strong answer mentions: the skeleton built from the commonest task, the extra unit for each kind tied at the maximum, and the max with the task count.

Check what stuck

1. A print server must print jobs one per minute, but jobs from the same user may not print within n minutes of each other. You want the shortest total time. Which approach fits best?

2. Why is the shown solution fast even when the answer is over a million time units?

3. A learner changes time + n to time + n + 1 in the cooling queue. Which input does it still get right?

Score 60% or more and the lesson is marked complete.