Task Scheduler

2 min read
LC-Medium
Binary-heap

Oct 21, 2022

3 years ago

LeetCode

Solution

Use a max heap + queue combo
We don't care about the names of the tasks- all we care about are the frequencies.
It is also better to deal with the most frequent tasks first- this way there is lesser idle time down the line. This is why we use the heap.
- To understand, look what happens when we don't process the most frequent tasks (A) first: There is way too much idle time
So count each task, add to a max heap where each element just has the remaining frequencies left:
- i.e. for AAABBBCC, your max heap would have [3, 3, 2]
Pop from max heap, reduce frequency by one. Let's say you take the task A. Occurs 3 times. Now it becomes 2.
Now, the important point here is that it cannot be processed for the idle time. Which is equal to current time + n. It cannot be processed again until the time == current_time + n
If we are at second 0 and n = 1, and A was processed, it cannot be considered for processing until time == n + 1 = 1. So another task will process (the next one from the max heap)
While the task is idle, the value along with the timestamp will be stored in a queue for later use.
Each iteration, we check the queue if the previously idle task is now able to be processed. If it is, we move it into the heap and process it.
The loop is run until both the heap and the queue are empty
IMPORTANT: WE ONLY PROCESS TASKS FROM THE HEAP. THE TASKS IN THE QUEUES WILL IMMEDIATELY GET ADDED BACK TO THE HEAP WHENEVER THEY CAN BE PROCESSED AGAIN.

Time	Space	Explanation
`O(n)`	`O(n)`

def leastInterval(self, tasks: List[str], n: int) -> int: tasks = [-x for x in Counter(tasks).values()] heapify(tasks) t = 0 q = deque() while tasks or q: if tasks: # Process task task = 1 + heappop(tasks) if task: q.append((task, t + n)) if q and q[0][1] == t: heappush(tasks, q.popleft()[0]) t += 1 return t