# 621. Task Scheduler

{% embed url="<https://leetcode.com/problems/task-scheduler/>" %}

因为存在 cooldown period，我们需要尽可能稀疏排开同一种任务，要尽可能总时间小，那就先排出现次数最多的任务（A），然后按出现次数逐个排进来，排到没得排了，就补齐 idle time，再排下一个 A。

### Heap

这种按照sort顺序逐个拿元素，先想到`heap`做（因为python 的heap默认最小堆，这边取value负数来实现最大堆）。

### Count Slot

1. 如果把 **most common task** A 的 cooldown period 塞满前，就分配完了所有任务，那么最后的时间长度就是 **# of slot + # of most common task**
2. 要是把 cooldown 塞满了还有 task 没有分配，那就要拓展 slot，相当于 reorder tasks，最后时间长度就等于 **total # of task**

{% tabs %}
{% tab title="Count Slot" %}

```python
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        mTask, mN = count.most_common()[0]
        tie = len([t for (t, freq) in count.items() if freq == mN])
        return max(len(tasks),
                  (mN-1) * (n+1) + tie)
```

{% endtab %}

{% tab title="Max Heap" %}

```python
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counter = [-x for x in Counter(tasks).values()]
        heapq.heapify(counter)
        
        res = 0
        while counter:
            slot = []
            for i in range(n+1):
                curr = heapq.heappop(counter)
                curr += 1
                res += 1
                if curr < 0:
                    slot.append(curr)
                # when the task type is used up
                if not counter:
                    # if slot exists, there will be next round
                    # we need to insert enough idle time
                    if slot: 
                        res += (n-i)
                    # if not, it means the final ending, no need to cooldown more
                    break
            for c in slot:
                heapq.heappush(counter, c)
                
        return res
```

{% endtab %}
{% endtabs %}
