LC 621 - Task Scheduler

Question

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there’s a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU 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 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.

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 <= 104
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

Links

Question here and solution here

Solution

concept

We keep 2 data structure, max heap and queue:

1. max heap keep track what are the current tasks that can be processed. (i.e. hot).
   1. take note that we would like to process tasks with the most frequency, we do not really care much which tasks, so in the max heap we only keep track the cnt. Each cnt represent a distinct task
2. queue will store (cnt, next_time_available) which are the tasks on cooldown.
   1. since we can only process one task at a time even if there is a tie in frequency among several tasks, only one task can be processed in max heap and add into queue for cooling down (if there is still task left for that alphabet). This means that there wont be a tie in queue. And since all task take 1 unit time and the waiting time n is the same for all task, this queue ‘s value will be sorted (i.e. smallest at queue[0])
   2. at each time step, we check if the first queue element has finished cooldown, if yes, we add it from queue (cold) to the max heap (hot)

code

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # max heap to keep track count
        # each count in this heap represent a task that can be processed
        counter = Counter(tasks)
        max_heap = [-cnt for cnt in counter.values()]
        heapq.heapify(max_heap)

        # a deque to keep track tasks that are on cooldown
        # each element is (-cnt, next available time)
        q = deque()
        time = 0

        while q or max_heap:
            time += 1
            # process the task
            if max_heap:
                cnt = 1 + heapq.heappop(max_heap)
                if cnt != 0:
                    q.append((cnt, time + n))

            # check if any task in q has finished cooldown
            if q and q[0][1] == time:
                    c, t = q.popleft()
                    heapq.heappush(max_heap, c)

        return time

Complexity

time: $O(n)$
space: $O(26)$