A LeetCode Daily Series — Day 96

In this article, we’ll explore a common problem related to scheduling CPU tasks with cooling intervals. We will analyze the problem and dive into two efficient solutions to optimize the scheduling process.

Task Scheduler - LeetCode leetcode.com

Can you solve this real interview question? Task Scheduler

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem

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 identical tasks must be separated by at least n intervals due to the cooling time.

The goal is to 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.

Using Efficient Approach: Heap and Queue

One efficient way to handle this problem is to use a max heap to always process the task with the highest frequency. Additionally, we can use a queue to manage the cooling period for each task.

def leastInterval(self, tasks: List[str], n: int) -> int:
    frequencies = Counter(tasks)

    maxHeap = [-cnt for cnt in frequencies.values()]
    heapq.heapify(maxHeap)

    time = 0

    q = deque()  # pairs of [-cnt, time when available]

    while maxHeap or q:
        time += 1
        if maxHeap:
            cnt = 1 + heapq.heappop(maxHeap)
            if cnt:
                q.append([cnt, time + n])
        if q and q[0][1] == time:
            heapq.heappush(maxHeap, q.popleft()[0])

    return time

Explanation

1. Count Task Frequencies: We use a Counter to count the occurrences of each task.
   • frequencies = Counter(tasks) will create a dictionary-like object where the keys are tasks and values are their counts.
2. Max Heap Initialization: We create a max heap using negative counts because Python’s heapq library only supports min heaps.
   • maxHeap = [-cnt for cnt in frequencies.values()] creates a list of negative counts.
   • heapq.heapify(maxHeap) transforms the list into a heap.
3. Queue Initialization: We use a deque to keep track of tasks during their cooling period.
   • q = deque() initializes an empty deque.
4. Time Simulation: We simulate each time unit:
   • time += 1 increments the time by one unit.
   • If there are tasks in the heap (if maxHeap:), we pop the most frequent task, decrement its count, and add it to the queue with its next available time.
     • cnt = 1 + heapq.heappop(maxHeap) pops the task with the highest frequency and decreases its count.
     • if cnt: checks if there are still more of this task to schedule and if so, it appends to the queue with its next available time time + n.
   • If the front of the queue is ready (if q and q[0][1] == time:), we push it back to the heap.
     • heapq.heappush(maxHeap, q.popleft()[0]) re-inserts the task back into the heap.
5. Return the Total Time: We return the total time units required to complete all tasks.

Time Complexity: O(T * log T), where T is the number of tasks. Each insertion and deletion from the heap takes logarithmic time.

Space Complexity: O(T), due to the heap and queue storage.

Using Efficient Approach 2: Mathematical Calculation

def leastInterval(self, tasks: List[str], n: int) -> int:
    frequencies = Counter(tasks)
    frequencies = dict(sorted(frequencies.items(), key=lambda item: item[1]))

    maxFrequency = frequencies.popitem()[1]
    idleTimes = (maxFrequency - 1) * n

    while frequencies and idleTimes > 0:
        idleTimes -= min(maxFrequency - 1, frequencies.popitem()[1])
    idleTimes = max(0, idleTimes)

    return len(tasks) + idleTimes

Explanation

1. Count Task Frequencies: We use a Counter to count the occurrences of each task.
   • frequencies = Counter(tasks) creates a dictionary-like object where the keys are tasks and values are their counts.
2. Sort Frequencies: We sort the frequencies in ascending order.
   • frequencies = dict(sorted(frequencies.items(), key=lambda item: item[1])) sorts the dictionary by values.
3. Calculate Maximum Frequency: We pop the task with the highest frequency.
   • maxFrequency = frequencies.popitem()[1] removes and returns the last item from the sorted dictionary, which is the task with the highest frequency.
4. Calculate Idle Times: We compute the initial idle times based on the most frequent task.
   • idleTimes = (maxFrequency - 1) * n calculates the initial idle times required.
5. Reduce Idle Times: We reduce the idle times by filling them with other tasks.
   • While there are still tasks and idle times to be filled (while frequencies and idleTimes > 0:), we decrease the idle times by the minimum of maxFrequency - 1 and the next highest frequency.
     • idleTimes -= min(maxFrequency - 1, frequencies.popitem()[1]) reduces the idle times.
   • idleTimes = max(0, idleTimes) ensures that idle times do not go below zero.
6. Return the Total Time: We return the sum of the total tasks and the remaining idle times.

Time Complexity: O(T log T), for sorting the frequency counts.

Space Complexity: O(T), for storing the task frequencies.

Conclusion

In this article, we discussed the problem of scheduling CPU tasks with cooling intervals and provided two efficient approaches to solve it. By using a max heap and queue or by mathematical calculation, we can minimize the intervals required to complete all tasks while adhering to the cooling period constraints.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.