leetcode: 621. Task Scheduler

task-scheduler.py

# time: O(nlogk) -> O(nlog1) ~ O(n)
# space: O(26) -> O(1)

from collections import Counter


class Solution:
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        # assume: tasks: AA
        #   n = 1:  A # A
        # . n = 2:  A # # A
        # . n = 3:  A # # # A
        #           ~~~~~~~ ~
        # let say   d1 .    d2
        # d1: n+1 -> (num(A) - 1) * (n+1)
        # d2: num(A) - (num(A) - 1) = 1
        counter = Counter(tasks)
        _, max_count = counter.most_common(1)[0]
        
        d1 = (max_count-1) * (n+1)
        d2 = sum(c == max_count for c in counter.values())
        return max(len(tasks), d1 + d2)