Task Scheduler Leetcode Problem 621 [Python Solution]

In the Task Scheduler problem, we are given an array of tasks represented by characters, where each character represents a different task.

These tasks can be done in any order, with each task taking one unit of time.

There is also a non-negative integer ‘n’ representing the cooldown period between two same tasks.

This cooldown period means that there must be at least ‘n’ units of time between any two instances of the same task.

The goal is to find the least number of units of time the CPU will take to finish all the given tasks.

Example:

Let’s take an example to understand the problem.

Suppose we have tasks ["A","A","A","B","B","B"] and ‘n’ is 2. The tasks can be completed as follows:

A -> B -> idle -> A -> B -> idle -> A -> B

In this example, there is at least 2 units of time between any two same tasks.

So, the least number of units of time the CPU will take to finish all the given tasks is 8.

Understanding Task Scheduler Constraints

The key constraints for this problem are as follows:
– The length of the tasks array is between 1 and 10,000.
– The tasks are represented by upper-case English letters.
– The integer ‘n’ can range from 0 to 100.

Task Scheduler LeetCode Problem Solution

To solve the Task Scheduler problem efficiently, we can use a priority queue (max heap) to keep track of the tasks that need to be processed.

We will follow these steps:

1. Count the Occurrences of Each Task

We start by counting the occurrences of each task using a Python Counter.

This will give us the frequency of each task.

2. Create a Max Heap

We create a max heap to prioritize tasks based on their frequency.

To do this, we negate the counts of the tasks and add them to the max heap.

The reason for negating the counts is that Python’s heapq library provides a min-heap by default.

By negating the counts, we effectively turn it into a max-heap.

3. Process Tasks

We start processing tasks while the max heap is not empty.

For each unit of time, we pop a task from the max heap, decrement its count by 1, and add it back to the max heap if its count is not zero.

Additionally, we add the task’s idle time (n) to the current time and store it in a queue for later processing.

4. Check for Idle Time

While processing tasks, we also check if there is any task in the queue that has become available for processing based on the idle time.

If such a task is found, we pop it from the queue and add it back to the max heap.

5. Return Total Time

After processing all tasks, we return the total time, which represents the least number of units of time the CPU will take to finish all the given tasks.

Task Scheduler Leetcode Problem Solution

View on GitHub ➹

def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        time = 0
        q = deque()  # pairs of [-cnt, idleTime]
        while maxHeap or q:
            time += 1

            if not maxHeap:
                time = q[0][1]
            else:
                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


# Greedy algorithm
class Solution(object):
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counter = collections.Counter(tasks)
        max_count = max(counter.values())
        min_time = (max_count - 1) * (n + 1) + 
                    sum(map(lambda count: count == max_count, counter.values()))
    
        return max(min_time, len(tasks))

Time and Space Complexity

The time complexity of this solution is O(n), where n is the length of the tasks array.

This is because we go through each task once.

The space complexity is also O(n) due to the max heap and queue used to store tasks.

Conclusion

In this blog post, we explored the Task Scheduler problem on LeetCode.

We discussed the problem statement, constraints, and provided an efficient Python solution using a max heap and a queue.

This solution helps find the least number of units of time the CPU will take to finish all tasks.

It’s important to understand the problem’s constraints and come up with an intuitive solution like the one presented here.

If you found this guide helpful, please consider liking and subscribing to support the our platform.

You can also check out my Patreon for additional support.

Feel free to comment, ask questions, make suggestions, and share this content with others.

Question Link