A processor must run every task in tasks, where each task is named by one uppercase letter.
Each task takes one time slot, and in every slot the processor either runs one task or sits idle.
Tasks may run in any order, but between two runs of the same task there must be at least n
other slots (running other tasks or idle). Return the smallest number of slots that runs every
task.
Example 1
- Input
- tasks = ["X", "X", "X", "Y", "Y"], n = 2
- Output
- 7
X Y idle X Y idle X: after each X come two other slots before the next one.Example 2
- Input
- tasks = ["P", "Q", "R", "P", "Q", "S"], n = 1
- Output
- 6
P Q P Q R S needs no idle slots, because there are enough different tasks to fill the gaps.Constraints
tasksholds 1 to 10⁴ tasks, each an uppercase letter fromAtoZ.- 0 ≤
n≤ 100
Show the pattern
Greedy, Heap
The most frequent task fixes the shape of the schedule: its copies must be spread out, and every other task can be tucked into the gaps between them. Counting and committing to that frame is a greedy argument (a max-heap simulation reaches the same answer).
See greedy in a visualiserShow the approach
Count each task. Let m be the highest count and t the number of tasks that appear m times.
Lay out the most frequent task first: m − 1 blocks of n + 1 slots, each starting with that
task, then a final row holding the t tasks that appear m times. Every other task fits into the
blocks' remaining slots, one copy per block, without breaking a cooldown. So
(m − 1) · (n + 1) + t slots are enough, and the most frequent task's own spacing shows that
fewer won't do.
If there are more tasks than that frame has room for, the extra ones can widen the blocks and no
slot needs to be idle, so the answer is simply len(tasks). The answer is the larger of the two.
A max-heap simulation gives the same result: each round of n + 1 slots, run the tasks with the
most copies left, then put them back with one copy fewer.
Time: O(len(tasks)) · Space: O(1): at most 26 counts