621. Task Scheduler

Loading...LeetCode

因为存在 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

Count Slot

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)

Max Heap

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