Leetcode 621. Task Scheduler

Problem

Leetcode 621 - Task Scheduler

Example:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.
After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.
With a cooling interval of 1, you can repeat a task after just one other task.

Input: tasks = ["A","A","A", "B","B","B"], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.
There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Approach

We can take max frequent amount of task first then second then third up to (n+1) amount.

After, we decrement all the frequencies. We keep this until we have completed all task.

We can formulize this to $time = (maxF-1) * (n+1) + maxCount$. Where maxF = max frequency, and maxCount = count of all max frequency (meaning that in [‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’], maxCount = 2 since there are 2 elements that have maxF = 3)

There is an edge case where n = 0, then we can return len(tasks)

Here is the Python code for the solution:

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = [0] * 26

        for ch in tasks:
            count[ord(ch) - ord('A')] += 1
        
        maxF = max(count)
        maxCount = 0
        for i in count:
            maxCount += 1 if i == maxF else 0
        
        time = (maxF-1) * (n+1) + maxCount

        return max(len(tasks), time)    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$