LC621 - Task Scheduler

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 there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

​Return the minimum number of intervals required to complete all tasks.

Example

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.

Solution

MaxHeap

Time and space complexity of this solution is $O(m \cdot n)$.

def leastInterval(self, tasks: List[str], n: int) -> int:
	taskList = {}
	for task in tasks:
		if task in taskList:
			taskList[task] = taskList[task] + 1
		else:
			taskList[task] = 1

	time = 0
	# Python doesn't have maxHeap, so use a minHeap and use neg value.
	maxHeap = [-count for count in taskList.values()]
	heapq.heapify(maxHeap)
	queue = deque()

	while maxHeap or queue:
		time += 1
		
		if maxHeap:
			count = 1 + heapq.heappop(maxHeap)
			# if nonzero
			if count:
				queue.append([count, time + n])
		if queue and queue[0][1] == time:
			heapq.heappush(maxHeap, queue.popleft()[0])
	return time