Tasks are letters, and each takes one unit of time. Two runs of the same task must be separated by at least n units, and the CPU may sit idle. Return the least number of units needed to finish all tasks.
DSA Animator › DSA Revision › Heap / Priority Queue › Task Scheduler
Remember: the most frequent task builds the frames. The answer can never be less than the number of tasks. The video solves Task Scheduler (LeetCode 621, Medium) with the Greedy by Max Frequency pattern from the Heap / Priority Queue topic, and you can replay every step in the interactive Task Scheduler animation.
Tasks are letters, and each takes one unit of time. Two runs of the same task must be separated by at least n units, and the CPU may sit idle. Return the least number of units needed to finish all tasks.
For tasks A, A, A, B, B, B with n equal to 2, the answer is 8. One schedule is A, B, idle, A, B, idle, A, B.
You could simulate every time unit with a max heap of remaining counts and a cooldown queue. That works, but there is a direct formula.
The most frequent task decides the shape of the schedule. If it appears max times, it creates max minus 1 gaps, each followed by a block of n plus 1 slots. So the frames need max minus 1, times n plus 1 slots. Every task that ties for the maximum count adds one more slot at the very end. If there are so many tasks that no idle slot is needed, the answer is simply the number of tasks.
A and B both appear 3 times, so max is 3, and 2 tasks tie for it. There are max minus 1, which is 2, frames of n plus 1, which is 3 slots each. That gives 6 slots: A, B, idle, A, B, idle. The two tied tasks add 2 slots at the end, A and B. The total is 6 plus 2, which is 8. The number of tasks is 6, which is smaller, so the answer is 8.
In code, count each letter in an array of 26. Find the maximum count, and how many letters have that count. Compute max minus 1, times n plus 1, plus the number of tied letters. Return the larger of that value and the number of tasks. It's O of n time and O of 1 space.
Remember: the most frequent task builds the frames. The answer can never be less than the number of tasks.