Where does the formula (maxCount − 1) · (n + 1) + maxTasks come from?

The most frequent task runs maxCount times and needs n slots after each run except the last. That gives maxCount − 1 full rows of n + 1 slots, plus one last row holding every task tied for the top count.

Why take the max with the number of tasks?

If there are more tasks than slots in the frame, the extra tasks simply widen the rows, and no idle slot is ever needed. Then the answer is the number of tasks, which is larger than the frame.

Can I solve it with a heap instead?

Yes. Simulate rounds of n + 1 slots, each time running the most frequent tasks from a max-heap and putting them back with one fewer. It gives the same answer in O(total · log 26); the counting formula is O(n) and shorter.

Task Scheduler

Find the fewest CPU intervals to run every task with n idle gaps between repeats, from a frame set by the most frequent task.

MediumSolve on LeetCode

Problem Understanding

Task Scheduler: given tasks labelled A–Z and a cooldown n, every interval the CPU runs one task or idles, and two runs of the same task must be at least n intervals apart. Return the fewest intervals needed to run every task.

Example: tasks = [A, A, A, B, B, B], n = 2 returns 8: A B idle A B idle A B.

Attempt 1: Simulate with a Heap

Run the schedule interval by interval: in each round of n + 1 slots, take the most frequent remaining tasks from a max-heap, run them, and push them back with one fewer. It is correct, but it simulates every interval. Counting alone tells us the answer, because only the most frequent task can force the CPU to idle.

The Intuition: The Most Frequent Task Builds a Frame

Say A is the most frequent task, with maxCount runs. Between two runs of A there must be n other slots, so lay the schedule out in rows of n + 1, one row per run of A:

A ? ?
A ? ?
A

That is maxCount − 1 full rows and a last row. Every task tied with A also needs a run in that last row, so the frame holds (maxCount − 1) · (n + 1) + maxTasks slots.

Fill the other tasks into the gaps column by column. A letter never lands twice in one row, so its runs are at least n + 1 apart. Gaps left over are idle time. If there are more tasks than gaps, the rows simply get longer and nothing idles, so the answer is max(len(tasks), frame). This is a greedy argument: the frame is a lower bound, and the fill shows it can always be met.

Interactive Walkthrough

The tally fills first. Once the top count is known the frame appears, one row per run of the most frequent task, read left to right as time. Each letter then fills down the columns; dashed cells are idle.

Dry Run Table

Input: tasks = [A, A, A, B, B, B], n = 2

Quantity	Value
counts	A = 3, B = 3
maxCount	3
maxTasks	2 (A and B)
frame	(3 − 1) · (2 + 1) + 2 = 8
answer	max(6, 8) = 8

The frame reads A B _ | A B _ | A B: two idle slots.

The Solution Template

Count, find the top count and its ties, and size the frame.

Task Scheduler Code

1var leastInterval = function(tasks, n) {
2    const counts = new Array(26).fill(0);
3    for (const t of tasks) counts[t.charCodeAt(0) - 65]++;
4    const maxCount = Math.max(...counts);
5    const maxTasks = counts.filter((c) => c === maxCount).length;
6    const frame = (maxCount - 1) * (n + 1) + maxTasks;
7    return Math.max(tasks.length, frame);
8};

Edge Cases & Common Mistakes

n = 0: no cooldown; the frame is never larger than the task count, so the answer is len(tasks).
Ties for the top count: forgetting maxTasks and adding 1 undercounts the last row: [A, A, B, B], n = 2 needs 5, not 4.
More tasks than slots: without max(len(tasks), frame) the formula returns too small a number, as in [A, C, A, B, D, B], n = 1.
Building the real schedule: the question asks only for the length; you never need to output the order.

Summary

Only the most frequent task can force idle time. It sets a frame of (maxCount − 1) · (n + 1) + maxTasks slots, every other task fits in the gaps column by column, and extra tasks just widen the rows. Return max(len(tasks), frame): O(n) time, O(1) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Jump Game II

Partition Labels