`heap`

`priority queue`

Given a letter (A to Z) array representing tasks. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval **n** that means between **two same tasks**, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the **least** number of intervals the CPU will take to finish all the given tasks.

**Example**

`tasks = ["A","A","A","B","B","B"], n = 2`

-> `8`

`A`

-`B`

-`#`

-`A`

-`B`

-`#`

-`A`

-`B`

## Solution

Use a max-heap to place most frequent elements in the first priority.

```
def leastInterval(tasks, n):
n += 1
ret = 0
d = collections.Counter(tasks)
heap = [-c for c in d.values()] # max-heap build trick
heapq.heapify(heap)
while heap:
temp = []
count = 0
for _ in range(n):
if heap:
c = heapq.heappop(heap)
count += 1
if c < -1:
temp.append(c + 1)
for item in temp:
heapq.heappush(heap, item)
ret += n if heap else count
return ret
```