Task Scheduler

Problem Statement

You are given an array of CPU tasks tasks, where tasks[i] is an uppercase english character from A to Z. You are also given an integer n.

Each CPU cycle allows the completion of a single task, and tasks may be completed in any order.

The only constraint is that identical tasks must be separated by at least n CPU cycles, to cooldown the CPU.

Return the minimum number of CPU cycles required to complete all tasks.

Example 1:

Input: tasks = ["X","X","Y","Y"], n = 2


Output: 5

Explanation: A possible sequence is: X -> Y -> idle -> X -> Y.

Example 2:

Input: tasks = ["A","A","A","B","C"], n = 3


Output: 9

Explanation: A possible sequence is: A -> B -> C -> Idle -> A -> Idle -> Idle -> Idle -> A.

Constraints:

  • 1 <= tasks.length <= 1000
  • 0 <= n <= 100

You should aim for a solution with O(m) time and O(1) space, where m is the size of the input array.

You should aim for a solution with O(m) time and O(1) space, where m is the size of the input array.

Hint 1

There are at most 26 different tasks, represented by A through Z. It is more efficient to count the frequency of each task and store it in a hash map or an array of size 26. Can you think of a way to determine which task should be processed first?

Hint 2

We should always process the most frequent task first. After selecting the most frequent task, we must ensure that it is not processed again until after n seconds, due to the cooldown condition. Can you think of an efficient way to select the most frequent task and enforce the cooldown? Perhaps you could use a data structure that allows for O(1) time to retrieve the maximum element and another data structure to cooldown the processed tasks.

Hint 3

We can use a Max-Heap to efficiently retrieve the most frequent task at any given instance. However, to enforce the cooldown period, we must temporarily hold off from reinserting the processed task into the heap. This is where a queue data structure comes in handy. It helps maintain the order of processed tasks. Can you implement this?

Hint 4

We start by calculating the frequency of each task and initialize a variable time to track the total processing time. The task frequencies are inserted into a Max-Heap. We also use a queue to store tasks along with the time they become available after the cooldown. At each step, if the Max-Heap is empty, we update time to match the next available task in the queue, covering idle time. Otherwise, we process the most frequent task from the heap, decrement its frequency, and if it’s still valid, add it back to the queue with its next available time. If the task at the front of the queue becomes available, we pop it and reinsert it into the heap.

Solution

Brute Force

def least_interval(tasks: List[str], n: int) -> int:
    count = [0] * 26
    for task in tasks:
        count[ord(task) - ord('A')] += 1


    available_tasks = []
    for i in range(26):
        if count[i] > 0:
            available_tasks.append([count[i], i])


    time = 0
    processed = []
    while available_tasks:
        max_index = -1
        for i in range(len(available_tasks)):
            is_available = True
            for j in range(max(0, time - n), time):
                if processed and processed[j] == available_tasks[i][1]:
                    is_available = False
                    break


            if is_available and (max_index == -1 or available_tasks[max_index][0] < available_tasks[i][0]):
                max_index = i


        time += 1
        current_task = -1
        if max_index != -1:
            current_task = available_tasks[max_index][1]
            available_tasks[max_index][0] -= 1
            if available_tasks[max_index][0] == 0:
                available_tasks.pop(max_index)
        processed.append(current_task)
    return time

Time complexity: O(t * n) Space complexity: O(t)