任务调度器如何用贪心计算最短时间？（LeetCode 621）

简化版

任务调度器的最短时间由「任务总数」和「最高频任务形成的冷却框架」共同决定。

设最高频次数为 maxFreq，有 maxCount 个任务都达到这个次数，则答案是 max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount)。

详细版

最难安排的是出现次数最多的任务，因为同一种任务之间至少要隔 n 个单位。假设最高频任务出现 maxFreq 次，可以把它们先放成 maxFreq - 1 个完整间隔块，每块长度是 n + 1，最后再放所有最高频任务的尾部。

公式是：

frame = (maxFreq - 1) * (n + 1) + maxCount
answer = max(任务总数, frame)

为什么要和任务总数取最大？因为当其他任务足够多时，它们可以把冷却空位完全填满，最终没有 idle，答案就是任务总数。当其他任务不够多时，必须插入 idle，答案由框架长度决定。

int leastInterval(char[] tasks, int n) {
    int[] cnt = new int[26];
    for (char t : tasks) cnt[t - 'A']++;
    int maxFreq = 0, maxCount = 0;
    for (int c : cnt) {
        if (c > maxFreq) {
            maxFreq = c;
            maxCount = 1;
        } else if (c == maxFreq) {
            maxCount++;
        }
    }
    int frame = (maxFreq - 1) * (n + 1) + maxCount;
    return Math.max(tasks.length, frame);
}

完整版教学

一、为什么最高频任务决定下界

冷却约束只限制相同任务之间的距离。出现次数少的任务更容易被塞进空隙，真正难安排的是出现次数最多的任务。若任务 A 出现 4 次，冷却时间 n=2，那么这些 A 至少要排成 A _ _ A _ _ A _ _ A 的形状，否则两个 A 之间距离不够。

这说明答案至少要覆盖最高频任务撑开的骨架。其他任务不是不重要，而是它们多数时候只是在填骨架里的空格。面试中这题考的就是能否先抓住「最紧约束」，再计算它带来的时间下界。

二、冷却框架怎么推出来

假设最高频次数是 maxFreq。把这些最高频任务分开，需要 maxFreq - 1 个间隔，每个间隔至少容纳 n 个其他时间单位，再加上当前最高频任务本身，所以每个完整块长度是 n + 1。

如果只有一个最高频任务，例如 A A A A 且 n=2：

A _ _ | A _ _ | A _ _ | A
  第1块  第2块  第3块   尾部

前三块长度都是 n+1=3，尾部只有最后一个 A。因此框架长度是 (4-1)*(2+1)+1=10。

记忆钩子：先让最高频任务排队站好，每两个之间空出 n 个位置；其他任务只是来填这些空位，填不满才会出现 idle。

三、多个最高频任务为什么要加 maxCount

如果 A 和 B 都出现 3 次，n=2，尾部不是只放一个任务，而要放所有最高频任务的最后一次。一个可行骨架是：

A B _ | A B _ | A B

这里 maxFreq=3，maxCount=2，框架长度是 (3-1)*(2+1)+2=8。如果仍然只加 1，就会低估尾部长度，导致答案错误。maxCount 统计的是达到最高频的任务种类数，它们共同占据每一轮的关键位置。

四、为什么还要和任务总数取最大

框架长度只是在 idle 可能存在时给出的下界。如果其他任务很多，它们可以填满所有空位，甚至让调度长度超过最高频框架。调度不能少于任务总数，因为每个任务都要占一个时间单位。

场景	例子	结果
其他任务少	`AAAB`, `n=2`	需要 idle，答案由框架决定
其他任务刚好填满	`AAABBC`, `n=2`	基本无空洞
其他任务很多	`AAABBBCCCDD`, `n=2`	答案通常等于任务总数

所以最终答案是 max(total, frame)，两个下界谁更大，谁就是最短时间。

五、用数字例子完整计算

以 tasks = [A,A,A,B,B,B]，n=2 为例。A 出现 3 次，B 也出现 3 次，所以 maxFreq=3，maxCount=2。

frame = (3 - 1) * (2 + 1) + 2
      = 2 * 3 + 2
      = 8
total = 6
answer = max(6, 8) = 8

一个调度是 A B idle A B idle A B。两个 A 之间距离为 3，两个 B 之间距离也为 3，满足冷却要求。

六、和堆模拟写法的关系

这题也可以用最大堆模拟：每轮取当前剩余次数最多的任务，执行后放入冷却队列。模拟法更直观，也适合输出具体调度序列；公式法更适合只求最短时间。

计数数组 -> 找最高频 -> 算框架 -> 与总任务数取最大
最大堆   -> 每轮取任务 -> 维护冷却 -> 模拟时间推进

如果面试只问 LeetCode 621 的最短时间，公式法更简洁；如果追问「怎么输出安排顺序」或任务种类很多且要动态加入任务，堆模拟更通用。

七、常见误区与追问

误区：答案直接等于 (maxFreq - 1) * (n + 1) + 1。 多个最高频任务并列时，尾部要加 maxCount，不是固定加 1。
误区：忘记和任务总数取最大。 其他任务足够多时没有 idle，答案就是总任务数。
误区：把冷却理解成中间必须有 n 个 idle。 中间可以是其他任务，不一定是 idle。
追问：如果 n 为 0 怎么办？ 没有冷却限制，公式也会返回任务总数。
追问：为什么只需要 26 个计数？ 原题任务是大写字母；若任务类型任意，可用哈希表统计。
追问：如何输出具体执行序列？ 用最大堆加冷却队列模拟，每个时间点选择可执行且剩余次数最多的任务。

八、加强记忆

任务调度器的核心锚点是「最高频任务先搭骨架，其他任务填空」。maxFreq 决定有多少轮，n+1 决定每轮最小跨度，maxCount 处理最高频并列的尾部长度。框架给出 idle 不足时的最短长度，任务总数给出无论如何都不能低于的长度，所以答案取二者最大。记住「骨架长度 vs 任务总数」这两个下界，公式就不会背错。

简化版

详细版