621.Task_Scheduler(Medium).md

621. Task Scheduler (Medium)

Date and Time: Aug 29, 2024, 14:10 (EST)

Link: https://leetcode.com/problems/task-scheduler/

Question:

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

​Return the minimum number of intervals required to complete all tasks.

Example 1:

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 cycles 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 cycle, you can do A again as 2 intervals have passed.

Example 2:

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.

Example 3:

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.

Constraints:

• 1 <= tasks.length <= 10^4

• tasks[i] is an uppercase English letter.

• 0 <= n <= 100

Walk-through:

maxHeap Approach:

1. save the counts of each task. And convert the counts into a maxHeap. We create a deque() so we can save the task with its cooldown time to the deque.

2. In the while loop, we incremenet the time and check if maxHeap has elements then we increment the current cnt (task), if new cnt != 0, we can append this task with [cnt, time + n] into deque(). Then we check the deque(), if deque[0][1] == time, so we know a previous task in deque() can be released back to maxHeap.

3. Finally, we just return the total time.

Greedy Approach:

1. Find the maximum counts elements are, and the maximum counts value. We can do it again by Counter() in Python.

2. We form intervals with the most frequent element's counts - 1, and each interval with n+1 elements.
   E.g. if n = 2, every interval goes like: [ _ , _ , _ ]. And we can form at most (max_frequent_elem_counts - 1) intervals, and each interval we can use (n + 1) elements, like [ A, _ , _ ] in Example 1.

3. Normally, the max_frequent_elem_counts should take the number of max_frequent_elem_counts lines, but we only use the max_frequent_elem_counts - 1 lines, because we want to count all the max_frequent_elem_counts elements in the last line, so they can all be processed in one interval.

4. Hence, we can count the total times by (max_frequent_elem_counts - 1) * (n+1) + nums_of_max_elem_counts, nums_of_max_elem_counts is just how many elements' counts = most counts.

5. In some cases, we can still arrange the scheduler so that it doesn't have two same tasks running before complete its idle time, hence the minimum task to be done is len(tasks). So the final answer should be max((max_frequent_elem_counts - 1) * (n+1) + nums_of_max_elem_counts, len(tasks))

Link: https://leetcode.com/problems/task-scheduler/solutions/699297/python-very-detailed-explanation-with-examples/comments/1885042

Python maxHeap Solution:

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-i for i in count.values()]
        heapq.heapify(maxHeap)
        
        time = 0
        deque = collections.deque()
        while maxHeap or deque:
            time += 1
            if maxHeap:
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt != 0:
                    deque.append([cnt, time + n])
            if deque and deque[0][1] == time:
                heapq.heappush(maxHeap, deque.popleft()[0])
        return time

Time Complexity: $O(n * log\ 26) = O(n)$, n is the length of tasks, since we need to store the counts of each task, it takes $O(n)$. Then, we perform heappop() and heappush(), which takes $O(log\ n)$ each.
Space Complexity: $O(1)$, because the maxHeap will have at most $O(26) = O(1)$.

Python Greedy Solution:

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)
        max_counts = max(counts.values())
        
        nums_max_counts = 0
        for val in counts.values():
            if val == max_counts:
                nums_max_counts += 1

        ans = (max_counts - 1) * (n + 1) + nums_max_counts
        return max(ans, len(tasks))

Time Complexity: $O(n)$
Space Complexity: $O(1)$