Task Scheduler
Problem
'A'..'Z' and taking one
time unit. In every unit it either runs one task or sits idle, and two runs of the
same label must be at least n units apart. Tasks may run in any order;
return the minimum total number of units needed.[A,A,A,B,B,B], n=2Output8 (AB_AB_AB)[A,C,A,B,D,B], n=1Output6[A,A,A,B,B,B], n=3Output101 ≤ tasks.length ≤ 104 · tasks[i] is an uppercase letter · 0 ≤ n ≤ 100
Try it yourself
class Solution {
public int leastInterval(char[] tasks, int n) {
}
}
maxF) forces a skeleton of
maxF - 1 frames of length n + 1, plus a last frame holding every task
that ties at maxF. Others fill the gaps; if they overflow, no idle is needed and
the answer is just tasks.length.Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.
Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.
Open the Greedy guide →Approaches
Brute ForceTick-by-Tick Simulation
O(26·T), T = answerSpace O(1)Advance time one unit at a time. Among tasks whose cooldown has expired, run the
one with the most remaining copies (otherwise idle), and mark it unavailable
until time + n + 1. Running the most frequent first keeps the longest
chain from becoming the bottleneck.
public int leastInterval(char[] tasks, int n) { int[] count = new int[26], nextFree = new int[26]; for (char t : tasks) count[t - 'A']++; int left = tasks.length, time = 0; while (left > 0) { int best = -1; for (int c = 0; c < 26; c++) { if (count[c] > 0 && nextFree[c] <= time && (best == -1 || count[c] > count[best])) best = c; } if (best != -1) { // otherwise this unit is idle count[best]--; left--; nextFree[best] = time + n + 1; } time++; } return time; }
Easy to trust, but walks through every idle unit one by one.
BetterMax-Heap, One Frame of n+1 at a Time
O(N log k)Space O(k)Fill each frame of n + 1 slots with up to n + 1
distinct tasks popped from a max-heap of remaining counts, then push the
decremented counts back. A full frame (or any frame followed by more work) costs
n + 1; only the final frame costs just its task count. k ≤ 26 is the
number of distinct tasks.
public int leastInterval(char[] tasks, int n) { int[] count = new int[26]; for (char t : tasks) count[t - 'A']++; PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); for (int c : count) if (c > 0) heap.offer(c); int time = 0; while (!heap.isEmpty()) { List<Integer> frame = new ArrayList<>(); for (int k = 0; k <= n && !heap.isEmpty(); k++) frame.add(heap.poll() - 1); for (int c : frame) if (c > 0) heap.offer(c); time += heap.isEmpty() ? frame.size() : n + 1; // last frame has no idles } return time; }
Skips idle units in bulk, but still processes tasks individually.
OptimalCounting Formula
O(N)Space O(1)Count letters, find maxF and how many letters maxCount
share it. The skeleton length is (maxF - 1)·(n + 1) + maxCount.
Remaining tasks fill idle gaps first; any surplus just stretches frames, so the
answer is the larger of the skeleton and tasks.length.
public int leastInterval(char[] tasks, int n) { int[] count = new int[26]; int maxF = 0, maxCount = 0; for (char t : tasks) maxF = Math.max(maxF, ++count[t - 'A']); for (int c : count) if (c == maxF) maxCount++; int skeleton = (maxF - 1) * (n + 1) + maxCount; return Math.max(skeleton, tasks.length); }
Closed form in one counting pass — no simulation at all.
n = 0: the skeleton becomes
maxF - 1 + maxCount ≤ tasks.length, so the answer is just the task count.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Tick-by-Tick Simulation | O(26·T), T = answer | O(1) |
| Better | Max-Heap, One Frame of n+1 at a Time | O(N log k) | O(k) |
| Optimal | Counting Formula | O(N) | O(1) |
- Dropping the
max(…, tasks.length)— with many distinct tasks there are no idles. - Forgetting tied max-frequency tasks: the last frame holds
maxCounttasks, not 1. - Counting a full
n + 1for the final heap frame — adds phantom idles.
- Draw the frames for
AAABBB, n=2:AB_ | AB_ | AB. - Explain why scheduling the most frequent task first is optimal (it is the bottleneck).
- If asked for the actual schedule, use the heap version; for the length alone, the formula.