LC 0621 [M] Task Scheduler - ALawliet/algorithms GitHub Wiki

math trick based on frequency

Let's say the most frequent tasks occur M times, and there are Mct groups of them.
When N > Mct, let's make our scheduling constraint strictly stronger by choosing N = Mct.
So from now on, let's suppose Mct <= N, and the most frequent tasks are denoted #A, #B, #C, ... #K.
Then we could schedule say, ABC...K__..._ABC...K__..._ABC...K__.....,
where A...K occurs Mct times,
_ denotes idle time,
and there is N space between A's.
This partial schedule would have length: L = (M-1) * (N+1) + Mct
Clearly, we need at least L intervals of time in our schedule to fit our given tasks.
class Solution:
    def leastInterval(self, tasks: List[str], N: int) -> int:
        max_L = len(tasks)
        tasks_count = list(Counter(tasks).values()) # [A:3, B:3] => [3, 3]
        M = max(tasks_count) # the highest count => 3
        MCT = tasks_count.count(M) # how often that highest count shows up => 2
        partial_L = (M-1) * (N+1) + MCT
        return max(max_L, partial_L)