Task Scheduler LeetCode 621 Deep Dive

LeetCode 621 Task Scheduler gives you an array of CPU tasks labeled A through Z and an integer n representing the cooldown interval. You must execute all tasks, but the same task type must wait at least n intervals before it can run again. During any interval you can either run a task or sit idle.

The goal is to find the minimum number of intervals required to finish all tasks. Idle intervals count toward the total, so you want to minimize them by filling cooldown gaps with different task types. The challenge is to pack tasks as densely as possible without violating the cooldown constraint.

This problem appears at medium difficulty and is a gateway to greedy scheduling. It rewards understanding the structure imposed by the most frequent task rather than trying to simulate every possible schedule exhaustively.

The most elegant solution uses a direct formula derived from the structure of the optimal schedule. Let maxFreq be the frequency of the most common task. The schedule consists of (maxFreq - 1) blocks of size (n + 1), each containing one instance of the most frequent task and n slots for other tasks or idle time. The last partial block contains all tasks tied for maxFreq.

The formula is: result = max((maxFreq - 1) * (n + 1) + countOfMaxFreq, tasks.length). The first term counts the idle-padded blocks. The second term handles the case where enough diverse tasks exist to fill all gaps — in that case no idle intervals are needed and the answer is simply the total number of tasks.

This formula runs in O(26) time to count frequencies and O(1) to compute the result. It is the most efficient possible solution since task labels are bounded to 26 characters.

The most frequent task creates the skeleton of the schedule. If task A appears 4 times with n=2, you must have gaps of at least 2 between each A: A _ _ A _ _ A _ _ A. That gives 3 gaps of size 2, plus the last A. The base structure is (4-1) * (2+1) + 1 = 10 intervals.

Other tasks fill these gaps from left to right. If you have enough other tasks to fill every gap, no idle intervals appear. In that case you might need more than 10 intervals — exactly tasks.length. The max() handles this: when tasks are dense enough to eliminate idle time, the answer is just the total count.

Idle intervals are only needed when the most frequent task is so dominant that gaps cannot be filled by other tasks. The formula counts exactly how many idles arise: idle = max(0, (maxFreq-1)*(n+1) + countOfMaxFreq - tasks.length). Minimizing idles is equivalent to maximizing the usage of gap slots.

The simulation approach uses a max-heap (priority queue) of task frequencies. In each round of (n+1) intervals, greedily pick the up to (n+1) most frequent remaining tasks, execute them, and decrement their counts. Re-add any task with remaining count greater than zero. Count the intervals used in this round — either (n+1) or the number of tasks left if fewer than (n+1) remain.

This simulation always produces the same answer as the formula. In each round you pick the most frequent tasks first, which is optimal — it ensures the most constrained tasks get scheduled as early as possible and minimizes idle time. Rounds are never extended beyond (n+1) intervals.

The simulation is more intuitive to reason about but less efficient: it runs in O(n * totalTasks / avgFreq) time due to heap operations per round. For interview purposes, knowing both approaches demonstrates deeper understanding and lets you explain the formula through the simulation.

When n=0 there is no cooldown constraint, so you can run tasks back to back in any order. The formula gives max((maxFreq-1)*1 + countOfMaxFreq, tasks.length) = max(tasks.length, tasks.length) = tasks.length. Correct: every task fills exactly one interval.

When all tasks are the same type, say tasks = [A, A, A, A] with n=2: maxFreq=4, countOfMaxFreq=1, formula = 3*3+1 = 10. Verify: A _ _ A _ _ A _ _ A — 10 intervals with 6 idles. There are no other tasks to fill the gaps, so all gaps become idle.

When many tasks share the maximum frequency, countOfMaxFreq grows and adds to the final block. With tasks = [A,A,B,B,C,C] and n=2: maxFreq=2, countOfMaxFreq=3, formula = 1*3+3 = 6. Since tasks.length is also 6, the answer is 6. The schedule is A B C A B C — no idles needed.

The Python formula solution is five lines: count frequencies with Counter, find maxFreq with max(), count ties with list.count(), apply the formula, and return the max with len(tasks). Time is O(n) for Counter and O(1) for the rest since there are only 26 possible task labels. Space is O(1) — the Counter has at most 26 entries.

The Python simulation uses a max-heap (negate frequencies for Python's min-heap). In each round pop up to (n+1) tasks, decrement, re-push non-zero. Track intervals as max(n+1, tasks popped) per round, repeating until the heap empties. Both approaches give identical results.

In Java, use an int[26] frequency array. For the formula: Arrays.sort(freq), read freq[25] as maxFreq, count ties from the right, apply max(formula, tasks.length). For the simulation: use a PriorityQueue with reverse order (Integer.compare(b,a)). The Java formula version has the same O(n) + O(26) complexity as Python.

Task Scheduler is part of a family of greedy scheduling problems. Course Schedule III (LeetCode 630) also involves scheduling tasks with deadlines, using a max-heap to greedily swap in longer-duration courses when a deadline is missed. The greedy principle is similar: always process the most constrained item first.

Meeting Rooms II (LeetCode 253) asks for the minimum number of conference rooms, using a min-heap of end times. Merge Intervals (LeetCode 56) handles overlapping time ranges. Both problems build the intuition for thinking about scheduling as a resource allocation problem where you want to minimize waste — idle time in Task Scheduler, unused rooms in Meeting Rooms.

Insert Delete GetRandom (LeetCode 380) and other design problems pair well here for interview preparation. Understanding Task Scheduler's formula deeply — why it is max(formula, totalTasks) — sharpens your ability to derive formulas rather than simulate, a skill that separates strong candidates from average ones.