#621 Task Scheduler
the problem
In plain words
Tasks are letters; each takes one interval. Two identical tasks must be at least n intervals apart (idle slots allowed). Return the minimum number of intervals to finish all tasks.
in tasks = [A,A,A,B,B,B], n = 2
out 8
A B idle A B idle A B.
in tasks = [A,C,A,B,D,B], n = 1
out 6
in tasks = [A,A,A,B,B,B], n = 3
out 10
- 1 ≤ tasks.length ≤ 10⁴
- tasks[i] is an uppercase letter
- 0 ≤ n ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy with a heapMath shortcut (closed form)
The most frequent task sets the skeleton: (maxCount − 1) full windows of n + 1 slots plus a final partial window. Other tasks fill the gaps — and if there are enough of them, no idle time is needed at all.
solutions
From brute force to optimal
In every window of n + 1 slots, run the tasks with the most remaining copies.
- Count tasks; max-heap of counts.
- Each window: poll up to n + 1 counts, decrement, push back non-zero.
- Add n + 1 per window (or the tasks run, for the last one).
Each of the N task runs costs one poll/offer on a heap of ≤ 26 counts: O(N log 26).
At most 26 counts.
class Solution { public int leastInterval(char[] tasks, int n) { int[] count = new int[26]; for (char t : tasks) count[t - 'A']++; PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder()); // remaining counts for (int c : count) if (c > 0) heap.offer(c); int time = 0; while (!heap.isEmpty()) { List<Integer> ranThisCycle = new ArrayList<>(); for (int slot = 0; slot < n + 1 && !heap.isEmpty(); slot++) { // one cooldown window ranThisCycle.add(heap.poll() - 1); // run the most urgent task } for (int left : ranThisCycle) if (left > 0) heap.offer(left); // a full window unless this was the very last one time += heap.isEmpty() ? ranThisCycle.size() : n + 1; } return time; }}answer = max(N, (maxCount − 1)·(n + 1) + numberOfTasksWithMaxCount).
- Count each letter; find maxCount.
- Count how many letters reach maxCount.
- Return the max of the frame size and N.
One counting pass + 26 checks.
26 counters.
class Solution { public int leastInterval(char[] tasks, int n) { int[] count = new int[26]; int maxCount = 0; for (char t : tasks) maxCount = Math.max(maxCount, ++count[t - 'A']); int tasksWithMax = 0; for (int c : count) if (c == maxCount) tasksWithMax++; // (maxCount − 1) full frames of length n + 1, then one last frame with the most frequent tasks int frames = (maxCount - 1) * (n + 1) + tasksWithMax; return Math.max(frames, tasks.length); // with many task types there is no idle time at all }}in the room
How to say it in the interview
talk track
- Draw the A _ _ A _ _ A frame for the example; the formula falls out of the picture.
- Explain the max with N: when there are many distinct tasks, gaps vanish.
traps
- Forgetting the
max(…, tasks.length)— the frame formula undercounts when no idling is needed.
what they ask next
Follow-ups
Return an actual schedule, not just its length?
Use the heap simulation: in each window of n + 1 slots, write down the tasks you poll, then fill the rest with "idle" (except in the last window).
Task Scheduler II (LC 2365): tasks must run in the given order?
No reordering, so no heap. Keep a map task → earliest allowed day. For each task: day = max(day + 1, allowed[task]); then allowed[task] = day + space + 1. Use long for days. O(n) time.
before you submit
Edge cases to test
- n = 0: no idle time ever — the answer is tasks.length.
- Many distinct tasks: the frame formula undercounts, so take the max with tasks.length.
- Several tasks tied for the max count: each adds one slot to the last frame.
practise next
Similar problems
- #767Reorganize StringMediumin Heaps
- #1046Last Stone WeightEasyin Heaps