LeetCode 621 · Medium · Heap / Priority Queue

Task Scheduler

A CPU runs one task per time unit, in any order, and must wait n units before running the same letter again, idling if nothing else is ready. Return the fewest units needed to finish every task.

O(t · log 26)time · t = units run
O(26)space
max-heap + queuerun the most frequent ready task

1–12 tasks, letters A–Z, at most 6 different · n from 0 to 4

maxHeap tasks ready to run · most left at the root

q cooling down · front on the left

maxHeap list PriorityQueue stores −count; shown as letter and count

Timeline what the CPU ran at each time unit

public int leastInterval(char[] tasks, int n) { int[] count = new int[26]; for (char task : tasks) { count[task - 'A']++; } List<Integer> negCounts = new ArrayList<>(); for (int c : count) { if (c > 0) { negCounts.add(-c); } } // min-heap of negated counts = max-heap of counts PriorityQueue<Integer> maxHeap = new PriorityQueue<>(negCounts); int time = 0; Deque<int[]> q = new ArrayDeque<>(); // {-cnt, idleTime} while (!maxHeap.isEmpty() || !q.isEmpty()) { time++; if (!maxHeap.isEmpty()) { int cnt = 1 + maxHeap.poll(); if (cnt != 0) { q.offer(new int[]{cnt, time + n}); } } if (!q.isEmpty() && q.peek()[1] == time) { maxHeap.offer(q.poll()[0]); } } return time;}
time
0
cnt
—
maxHeap
[]
q
[]

Why it works

  1. Brute force tries schedules: at each unit, branch on every ready task. Exponential, and it still needs a rule for which choice is best.
  2. Greedy rule: run the ready task with the most copies left. The most frequent task is what forces idle time, so spending it early leaves the most room to fill its cooldowns with other letters. The heap hands out that task; the queue holds tasks until time + n, in the order they ran, so its front is always the next to be ready.
  3. Cost: one loop pass per time unit, each with O(log 26) heap work, so O(t) for t units, with at most 26 entries anywhere: O(1) space. The letters on this page are for reading only; the code stores just counts, since which letter it is never matters.
  4. Pitfall: PriorityQueue is a min-heap by default, so store -cnt (or pass Collections.reverseOrder() and subtract 1 instead). Then 1 + maxHeap.poll() is one fewer copy left, and it hits 0 when the task is finished, which is why only nonzero counts go back in the queue.
  5. Math shortcut: the answer is Math.max(tasks.length, (maxCount − 1) * (n + 1) + numberOfTasksWithMaxCount): one counting pass over the tasks, with no simulation. The heap version generalises to "also print the schedule".