Task Scheduler

Today we are going to solve this leetcod/task-scheduler. This is a good problem and would need some thinking to solve it thorughly.

Heapqueue Approach

In the question one had to find the least time a computer would take to complete some tasks, while completing task computer has to take some time before it can do the same task again so either do another task or do nothing for that unit of time. We are asked to find the least time it would take to complete all the task.

To solve this question we will take a maxHeap (max-priority-queue) why we will do this just imagine what would be best way to arrange solve the task that we can do other task while its in cooldown period obviously the one with the most count cause then after other task we can take those task not worry about wasting time while less count task is in cooldown period.

The algorithm is pretty simple:

1. Create a maxHeap from the count of tasks provided by the problem.
2. Create a queue to store the updated count after one task is done and time when when its in cooldown period.
3. Create the time variable to start the count when the task is being done by computer.
4. start while loop until any one queue or maxHeap contains task to complete.
5. inside the loop increase the time by 1.
6. check if the maxHeap contains any task to do. If there is pop it minus one from the count and calculate the cooldown for it by adding the current time and the cooldown variable n. Then insert both variable inside the queue. I will not do it if the count of any task become 0 then it will just be skipped.
7. Now check if queue’s top element cooldown time is equal to the current time variable. If it is pop it and insert into the maxHeap.
8. repeat step 4 to 7 until both queue and maxHeap is empty.
9. When loop stops return the time variable.

Now the code look like this. (as python heapq library only contains min-heap we i am going to treat those number in count as negative and instead of minus 1 from tasks count I will add it everything else will be same and when the task number reaches 0 will not add it inside the queue.)

import heapq
from collections import Counter, deque
from typing import List


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

Now lets see whats the time complexity, for making a heap we take O(n) (n is the number of tasks) time and every other operation is O(1) (the insertion in queue) or O(log(n)) (the insertion in heap) but in worst case (where all the task is of same type) the loop has to theoritically run for O(n * m) (where m is the cooldown time). And space complexity is O(n) cause space taken by heap is O(26) (since tasks can be only upper case english alphabet letters) which corresponds to O(1) so it is not included into the space complexity and we only count the space taken by taks list.

Time Complexity: O(n*m)
Space Complexity: O(n)

If you got any issue or just want to talk to me about something ping me up in my socials.