（贪心）621. 任务调度器

2026/10/27 10:22:43

题目

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

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

示例 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 <= tasks.length <= 10<sup>4</sup>
tasks[i]是大写英文字母
0 <= n <= 100

算法

贪心思想：先由 maxTimes 和 n 计算冷却约束，再用 maxCount 处理并列最高频次的任务，最后考虑任务总数 tasks.length。

maxTimes：出现次数最多的任务，出现了多少次；
maxCount：出现次数等于maxTimes的任务种类数。

每个任务执行需要一个时间单位；相同任务之间必须至少间隔n个时间单位。不足以执行其他任务时，可以插入空闲时间idle

假设任务为：tasks = [‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’]; n = 2;

两个 A 之间至少需要两个时间单位：A -> idle -> idle -> A
也可以用其他任务填充空闲时间：A -> B -> C -> A
因为 A 和 A 之间已经间隔了两个任务时间单位。
对于上面的输入，一种最优排程是：最终需要 8 个时间单位
```
时间： 1 2 3 4 5 6 7 8 任务： A B idle A B idle A B
```

先统计每种任务出现的次数：因为出现次数最多的任务，通常决定了排程需要多长时间。

如果 A 出现 5 次，且冷却时间 n = 3，那么任务 A 至少需要安排成：A _ _ _ A _ _ _ A _ _ _ A _ _ _ A
无论其他任务是什么，都不能让这 5 个 A 之间的冷却约束消失。
因此，我们先统计频次，再找出出现次数最多的任务。

maxTimes：单个任务的最大出现次数。出现次数最多的任务，出现了多少次。

maxTimes - 1：表示最高频次任务的出现次数之间，有多少段间隔需要满足冷却约束。
同一个任务执行完后，需要等待 n 个时间单位，才能再次执行。所以，相邻两次相同任务的执行位置，至少相差：n+1
所以得到公式：(maxTimes−1)(n+1)(\text{maxTimes}-1)(n+1)(maxTimes−1)(n+1)

maxCount：出现次数等于maxTimes的任务种类数。

如果有多个任务都达到了最大频次，它们都需要放在最终一组的末尾，用来计算排程的最短长度。

上述的公式只是最高频次任务最后一次出现的最早位置，还没有考虑其他并列最高频次的任务。
如：A = 3 次；B = 3 次；C = 2 次；n = 2
- 则：maxTimes = 3; maxCount = 2;
- A 和 B 的第三次出现，都不能早于时间位置：(3−1)(2+1)=6(3-1)(2+1)=6(3−1)(2+1)=6
- 但是，A 和 B 不能在同一个时间单位执行，因此它们的最后一次出现必须占据两个不同的位置。
- 最早可以是：整个排程至少需要从位置 0 延伸到位置 7，也就是 8 个时间单位。
```
时间位置： 6 7 任务： A B
```
因此：+ maxCount 的原因是：有 maxCount 种最高频次任务，它们最后一次出现必须占据不同的时间槽。

tasks.length是所有任务的数量，每个任务至少需要一个时间单位。所以，无论冷却时间如何安排，都有：最短时间>tasks.length最短时间 > tasks.length最短时间>tasks.length

如：tasks = [A, A, A, B, B, B, C, C, D, D]；n = 2
maxTimes = 3; maxCount = 2;
公式计算：res = (3 - 1) * (2 + 1) + 2; res = 8；
但是，8 个时间单位不可能执行完 10 个任务。
如果其他任务足够多，可以填满冷却间隔，就不需要插入空闲时间，执行这些任务至少需要 tasks.length 个时间单位。我们执行任务所需的时间，就是任务的数量

最终返回： (maxTimes - 1) * (n + 1) + maxCount

代码

import java.util.Arrays; class Solution { public int leastInterval(char[] tasks, int n) { // 1. 统计每种任务出现的次数 // A 对应 buckets[0]，B 对应 buckets[1]，依此类推 int[] buckets = new int[26]; for (int i = 0; i < tasks.length; i++) { buckets[tasks[i] - 'A']++; } // 2. 按任务出现次数从小到大排序 // 排序后，最大频次位于 buckets[25] Arrays.sort(buckets); // 出现次数最多的任务，其出现次数 int maxTimes = buckets[25]; // 出现次数最多的任务有多少种 // 至少有一种任务达到最大频次 int maxCount = 1; // 从后往前统计有多少种任务的频次等于 maxTimes // 因为数组已排序，相同的最大值会连续出现在末尾 for (int i = 25; i >= 1; i--) { if (buckets[i] == buckets[i - 1]) { maxCount++; } else { // 遇到不同的频次，说明已经统计完所有最大值 break; } } // 3. 根据最高频次任务计算所需的最短排程长度 int res = (maxTimes - 1) * (n + 1) + maxCount; // 4. 最终时间不能少于任务总数 // 如果其他任务足够多，可以填满所有冷却空隙 return Math.max(res, tasks.length); } }