621. 任务调度器 [medium]

https://leetcode-cn.com/problems/task-scheduler/

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 

提示：

任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。

通过次数24,933 | 提交次数50,257

First Try

2020-06-27

这些题都是第一眼看上去有点懵逼，仔细想一想就能找到套路解决，这一波是用前几道刚学会到heap堆排序方法搞定的，思路非常自然清晰，不过时间排名算是普通。有几个tricky的点写的时候容易出bug，还是得多练习关注这些边界状态。

不过看题解有好几种其他解法，还是得花时间看一眼，估计花的时间还要比自己做题久。。。

import collections
import heapq

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        # 关键路径做法，每次都优先处理较长的任务
        counter = collections.defaultdict(int)
        for t in tasks:
            counter[t] += 1
        heap = []
        for k, v in counter.items():
            heapq.heappush(heap, (-v, k))
        # print(heap)
        duration = 0
        while heap:
            tmp = []
            c = 1
            # 间隔n个，其实一轮就有n+1个元素，容易出错
            while c <= n + 1 and len(heap):
                v, k = heapq.heappop(heap)
                if v + 1 != 0:
                    tmp.append((v+1, k))
                c += 1  # 此时c已经大于n + 1
                # print(v, k, c)

            if len(tmp):
                duration += (n + 1)
                for t in tmp:
                    heapq.heappush(heap, t)
             # 一波带走已经没有了， c-1是个容易出错的点
             # 如果heap中还有其他元素，则c-1也刚好是n+1,继续下一轮
            else: 
                duration += (c - 1) 
        return duration 

执行用时：276 ms, 在所有 Python 提交中击败了18.73%的用户
内存消耗：14 MB, 在所有 Python 提交中击败了100.00%的用户

621. 任务调度器 [medium]​

First Try​

621. 任务调度器 [medium]

First Try