> For the complete documentation index, see [llms.txt](https://www.vjssn.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.vjssn.dev/practice/24-06-17/lc621-task-scheduler.md).

# 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)$$.

```python
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
```