176 - 621 任务调度器

题目

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

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

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

示例 1：

输入: tasks = ["A","A","A","B","B","B"], n = 2 输出: 8 执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

注：

1. 任务的总个数为 [1, 10000]。

2. n 的取值范围为 [0, 100]。

解答

• 相同任务要间隔n

https://leetcode.com/problems/task-scheduler/discuss/104496/concise-Java-Solution-O(N)-time-O(26)-space

就一个非常花哨的做法

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        c = [0]*26
        for task in tasks:
            c[ord(task)-65] += 1
        c.sort()
        i = 25
        while i >= 0 and c[i] == c[25]:
            i -= 1
        return max(len(tasks), (c[25]-1)*(n+1)+25-i)

Runtime: 448 ms, faster than 70.38% of Python3 online submissions for Task Scheduler.

Memory Usage: 13 MB, less than 100.00% of Python3 online submissions for Task Scheduler.

突然发现，for循环结束后，task这个变量还能存在作用域里面。。。这是作用域污染了吧😂

不用sort的做法

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        length = len(tasks)
        c = [0]*26
        m = 0
        maxNum = 0
        for task in tasks:
            c[ord(task)-65] += 1
            if c[ord(task)-65] > m:
                m = c[ord(task)-65]
                maxNum = 1
            elif c[ord(task)-65] == m:
                maxNum += 1
        return max(length, (m-1)*(n+1)+maxNum)

Runtime: 492 ms, faster than 54.73% of Python3 online submissions for Task Scheduler.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Task Scheduler.