Description
Schedule uppercase-letter tasks in any order, with at least n time slots between equal letters. Every task takes one slot; idle slots are allowed. Return the smallest total duration.
Solution
from collections import Counter
def least_interval(tasks, n):
counts = Counter(tasks)
highest = max(counts.values())
ties = sum(value == highest for value in counts.values())
return max(len(tasks), (highest - 1) * (n + 1) + ties)Examples
Example 1
- Input
[["A","A","A","B","B","B"],2]- Output
8
A B idle A B idle A B meets both cooldowns.
Example 2
- Input
[["A","A","A","B","B","B"],0]- Output
6
No cooldown requires no idle slots.
Example 3
- Input
[["A"],4]- Output
1
A single task has no repeated occurrence.
Approach
Count the most frequent task and how many tasks tie for that frequency. Their required spacing forms (maximum frequency - 1) blocks of length n + 1 plus the tied final tasks. The answer is the greater of that bound and the number of tasks.
Time & space
O(t) time and O(1) auxiliary space for 26 task types, where t is the task count.