621. 任务调度器

题目链接（中等）

题目描述

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

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

数据范围：

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

示例

示例 1：

输入： tasks = ["A","A","A","B","B","B"], n = 2
输出： 8
解释：
在完成任务 A 之后，你必须等待两个间隔。对任务 B 来说也是一样。在第 3 个间隔，A 和 B 都不能完成，所以你需要待命。在第 4 个间隔，由于已经经过了 2 个间隔，你可以再次执行 A 任务。

示例 2：

输入： tasks = ["A","C","A","B","D","B"], n = 1
输出： 6
解释： 一种可能的序列是 A -> B -> C -> D -> A -> B。由于冷却间隔为 1，你可以在完成另一个任务后重复执行这个任务。

示例 3：

输入： tasks = ["A","A","A","B","B","B"], n = 3
输出： 10
解释： 一种可能的序列为 A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B。只有两种任务类型，A 和 B，需要被 3 个间隔分割。这导致重复执行这些任务的间隔当中有两次待命状态。

核心思路

两种解法：

1. 模拟：按时间顺序逐步分配任务，每次选「剩余次数最多且不在冷却中」的任务，用 nextValid 数组记录每个任务的最早可执行时间；
2. 构造（桶思想）：把任务排成矩阵，按「出现最多的任务」的列来估算最短时间，答案是 (maxExec - 1) * (n + 1) + maxCount 与 len(tasks) 中的较大值。

构造法是本题最优解，代码极短。

---

方法一：模拟

思路及解法

贪心策略：在每个时间点，选择「剩余执行次数最多且不在冷却中」的任务执行。

为什么选剩余次数最多的：

• 冷却是为了分散任务，让 CPU 尽量不空闲；
• 把剩余次数多的任务优先执行，能有效减少 CPU 的待命时间。

数据结构：

• nextValid[i]：任务 i 最早可以执行的时间；
• rest[i]：任务 i 剩余执行次数；
• time：当前时间。

流程：

1. 用 Counter 统计每种任务的次数；
2. 循环 len(tasks) 次（每次执行一个任务）：
   • time += 1；
   • 计算所有还有剩余次数的任务中，nextValid 的最小值，将 time 快速跳到这个最小值（跳过待命状态）；
   • 在不在冷却中（nextValid[i] <= time）且有剩余次数的任务中，选剩余次数最多的作为 best；
   • 执行 best：nextValid[best] = time + n + 1，rest[best] -= 1；
3. 返回 time。

为什么要「快速跳到最小的 nextValid」：

如果直接 time += 1 逐秒推进，CPU 待命时还要浪费时间遍历所有任务，效率低。直接把 time 跳到「最早可以执行任务的时间」即可跳过待命状态。

代码

from collections import Counter

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        freq = Counter(tasks)
        m = len(freq)
        next_valid = [1] * m
        rest = list(freq.values())

        time = 0
        for _ in range(len(tasks)):
            time += 1
            # 快速跳过待命状态
            min_next = min(next_valid[j] for j in range(m) if rest[j] > 0)
            time = max(time, min_next)

            # 选剩余次数最多且不在冷却中的任务
            best = -1
            for j in range(m):
                if rest[j] > 0 and next_valid[j] <= time:
                    if best == -1 or rest[j] > rest[best]:
                        best = j

            next_valid[best] = time + n + 1
            rest[best] -= 1

        return time

复杂度分析

• 时间复杂度：$O(|tasks| \cdot |\Sigma|)$，$|\Sigma| \le 26$ 是任务种类数。
• 空间复杂度：$O(|\Sigma|)$。

---

方法二：构造（桶思想）✅ 推荐

思路及解法

核心思想：把任务排成矩阵，行优先填充。

步骤：

1. 找出执行次数最多的任务的次数 maxExec；
2. 统计有多少个任务执行了 maxExec 次，记为 maxCount；
3. 用一个 (maxExec - 1) × (n + 1) 的矩阵来安排这些任务：
   • 每个「满行」有 n + 1 列；
   • 最后一行的长度为 maxCount；
4. 得到总时间 (maxExec - 1) * (n + 1) + maxCount；
5. 但如果任务太多，可能填满了所有格子，不会有空闲。此时答案是 len(tasks)；
6. 返回两者中的最大值。

为什么是 (maxExec - 1) * (n + 1) + maxCount？

以 tasks = ["A","A","A","B","B","B"], n = 2 为例：

• maxExec = 3（A、B 都出现 3 次）；
• maxCount = 2（两个任务都是最大次数）；
• 矩阵形状：(3-1) × (2+1) = 2 × 3，最后一行长度 2：

A B _
A B _
A B

总时间 = 2 * 3 + 2 = 8。

为什么跟 len(tasks) 取最大值？

如果任务种类很多、次数很平均，矩阵不会「满」，(maxExec - 1) * (n + 1) + maxCount 会小于 len(tasks)，此时不用等待，答案就是 len(tasks)。

反之，任务种类很少但某个任务特别多时，就会出现大量待命，矩阵公式给出更大的答案。

代码

from collections import Counter

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        freq = Counter(tasks)

        max_freq = max(freq.values())                     # 最多出现次数
        max_count = sum(1 for v in freq.values() if v == max_freq)  # 多少任务达到最大次数

        return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

复杂度分析

• 时间复杂度：$O(|tasks| + |\Sigma|)$，统计频率 $O(|tasks|)$，找最大值和计数 $O(|\Sigma|)$。
• 空间复杂度：$O(|\Sigma|)$。

---

两种方法对比

方法	时间	空间	特点
模拟	$O(	tasks	\cdot	\Sigma	)$	$O(	\Sigma	)$	思路直观，适合讲清过程
构造	$O(	tasks	+	\Sigma	)$	$O(	\Sigma	)$	代码极短，面试首选

推荐：

• 面试开场：先讲模拟，把「贪心选剩余次数最多的任务」这个思路讲清楚；
• 追问优化：再讲构造法，展示数学推导和桶思想。

---

关键细节

1. 为什么贪心选「剩余次数最多的任务」

在任意时间点，如果有多个任务不在冷却中，选择剩余次数多的任务能最大化利用 CPU 空闲时间。剩余次数少的那几个任务，即使留到后面，因为它们需要的执行次数少，不会成为瓶颈。

2. 桶思想的矩阵排布

把出现次数最多的任务作为「桶的边界」，列数固定为 n + 1：

• 每一列代表同一时间点最多容纳的任务数（同一任务必须间隔 n，所以两行之间需要 n + 1 个时间片）；
• 行数 = maxExec - 1（因为最后一行可能不满）。

3. 为什么是 n + 1 而不是 n

因为两个相同任务之间至少间隔 n 个时间片，加上任务本身占一个时间片，所以同一任务相邻两次出现之间至少隔了 n + 1 个时间片。

因此「桶」的宽度是 n + 1。

4. 何时取 len(tasks)

如果任务种类足够多，多到能够填满每一个「冷却槽」，此时不会有 CPU 待命，总时间就等于任务数。

例如 tasks = ["A","B","C","D","E","F"], n = 1：

• maxExec = 1，maxCount = 6；
• 公式给出 0 * 2 + 6 = 6；
• len(tasks) = 6；
• 取最大值仍是 6，此时答案就是 6。

5. 一个直观的图形理解

maxExec = 3, maxCount = 2, n = 2

A B _
A B _
A B

时间线：A B _ A B _ A B  → 共 8 个时间片

6. 与「模拟法」的等价性

两种方法在本质上给出同一个答案。构造法是从「矩阵结构」的角度推导，模拟法是从「时间线」的角度推导。

---

总结

• 核心问题：任务调度，相同任务之间至少间隔 n；
• 模拟法：
  • 每次选「剩余次数最多且不在冷却中」的任务；
  • 用 nextValid 记录每个任务的最早可执行时间；
  • 快速跳过待命状态；
  • 时间 $O(|tasks| \cdot |\Sigma|)$、空间 $O(|\Sigma|)$；
• 构造法（推荐）：
  • 找出最多执行次数 maxExec 和达到该次数的任务数 maxCount；
  • 最短时间 = max((maxExec - 1) * (n + 1) + maxCount, len(tasks))；
  • 时间 $O(|tasks| + |\Sigma|)$、空间 $O(|\Sigma|)$；
• 通用套路：「相同元素之间至少间隔 n」→ 桶思想 / 矩阵排布。

相关题目

• LC 358. K 距离间隔重排字符串（相似但不完全相同）
• LC 767. 重构字符串（贪心 + 堆）
• LC 1054. 距离相等的条形码（贪心 + 堆）
• LC 1405. 最长快乐字符串（贪心 + 堆）