任务调度器

难度: Medium

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的 最短时间间隔 。

示例 1：

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

示例 2：

输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类

示例 3：

输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
     A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

1 <= tasks.length <= 10⁴
tasks[i] 是大写英文字母
0 <= n <= 100

Submission

运行时间: 45 ms

内存: 17.7 MB

from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if n == 0:
            return len(tasks)
        
        # 计算每个任务的频率
        task_freq = Counter(tasks)
        
        # 找到最高频率
        max_freq = max(task_freq.values())
        
        # 计算最高频率的任务数量
        max_count = sum(1 for f in task_freq.values() if f == max_freq)
        
        # 计算至少需要的时间单位
        # (max_freq - 1) * (n + 1)表示在最高频率的任务之间插入间隔后所需的时间单位
        # 加上max_count表示最高频率的任务本身所需的时间单位
        # 最后加上可能剩余的任务
        return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

Explain

该题解的思路是统计任务的频率，找到频率最高的任务。根据最高频率和冷却时间，计算完成所有任务所需的最短时间间隔。具体来说： 1. 如果冷却时间 n 为0，直接返回任务的总数，因为任务可以连续执行。 2. 统计每个任务的频率，找到最高频率 max_freq。 3. 计算最高频率的任务数量 max_count。 4. 计算最短时间间隔，取以下两者的较大值： - 任务总数 len(tasks)。 - (max_freq - 1) * (n + 1) + max_count，其中 (max_freq - 1) * (n + 1) 表示在最高频率的任务之间插入冷却时间后所需的时间单位，max_count 表示最高频率的任务本身所需的时间单位。

时间复杂度: O(n)

空间复杂度: O(1)

from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if n == 0:
            return len(tasks)
        
        # 计算每个任务的频率
        task_freq = Counter(tasks)
        
        # 找到最高频率
        max_freq = max(task_freq.values())
        
        # 计算最高频率的任务数量
        max_count = sum(1 for f in task_freq.values() if f == max_freq)
        
        # 计算至少需要的时间单位
        # (max_freq - 1) * (n + 1)表示在最高频率的任务之间插入间隔后所需的时间单位
        # 加上max_count表示最高频率的任务本身所需的时间单位
        # 最后取任务总数和计算结果的较大值，以处理可能剩余的任务
        return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

Explore

在算法中，最高频率任务的数量`max_count`是指有多少种任务的出现频率等于所有任务中出现频率最高的值。这个计算通过统计在任务频率字典`task_freq`中频率值等于`max_freq`的任务种类来实现。具体的计算方法是通过一个生成器表达式遍历`task_freq.values()`，对于每一个频率值`f`，如果`f`等于`max_freq`，则计数器加一。这个值的计算对于理解任务调度的时间间隔至关重要，因为在插入冷却时间的间隔中，最高频率的任务会决定必须等待的最少时间段。例如，如果最高频率的任务有多种，那么在最后一个周期中，这些任务将不需要额外的冷却时间即可依次执行，从而影响总的任务完成时间。

在任务种类非常多但每种任务的出现频率都很低的情况下，算法仍然有效并且效率较高。通过使用`Counter`来统计每种任务的频率，算法的时间复杂度主要是O(N)，其中N是任务列表的长度。尽管任务种类多，但由于每种任务的频率低，计算最高频率`max_freq`和最高频率任务的数量`max_count`通常也是高效的。这种情况下，最终计算的时间间隔可能接近于任务的总数，因为高频任务较少，导致冷却时间的影响减小。因此，这种情况下的计算并不会引入不必要的复杂性。

使用`Counter`来统计元素频率是一种非常高效的方法，特别是在处理大规模数据时。`Counter`是`collections`模块中提供的一个字典子类，专门为快速计数场景设计。它在内部实现了散列表（哈希表），因此统计每个元素的出现次数的时间复杂度是O(1)，整体上对于列表的遍历是O(N)，其中N是列表的长度。即使面对大量数据，`Counter`能够快速准确地计算出各个元素的频率，因此在性能上是非常可靠的。