一、题目描述LeetCode 621「任务调度器」给定一个字符数组tasks其中每个字符表示一种 CPU 任务例如tasks [A, A, A, B, B, B]同时给定一个整数n表示冷却时间。CPU 每个时间单位只能执行一个任务或者处于空闲状态idle。题目要求两个相同任务之间必须间隔至少n个时间单位。也就是说如果当前执行了任务A那么下一次执行A之前必须先经过至少n个其他时间间隔。要求返回完成所有任务所需要的最短时间。二、示例分析示例一tasks [A,A,A,B,B,B] n 2任务频率为A: 3 B: 3由于A出现了 3 次两个A之间必须至少隔 2 个时间单位。一种最优安排是A - B - idle - A - B - idle - A - B总时间为8所以答案是8示例二tasks [A,C,A,B,D,B] n 1任务频率为A: 2 B: 2 C: 1 D: 1一种合法安排是A - B - C - D - A - B因为冷却时间为 1相同任务之间只需要隔一个任务即可。总时间为6所以答案是6示例三tasks [A,A,A,B,B,B] n 3任务频率为A: 3 B: 3由于冷却时间更长必须插入更多空闲时间。一种最优安排是A - B - idle - idle - A - B - idle - idle - A - B总时间为10所以答案是10三、问题本质这道题的本质不是简单地排序任务也不是盲目模拟 CPU 执行过程。它真正考查的是如何在冷却时间限制下让出现次数最多的任务尽可能合理分布从而减少 idle 的数量。所有任务中出现次数最多的任务对最终时间影响最大。例如A A A A如果n 2那么这些A之间至少需要这样摆放A _ _ A _ _ A _ _ A可以看到频率最高的任务会强制制造出一些“间隔槽位”。其他任务能否填满这些槽位决定了最终是否需要idle。四、核心贪心思想设出现次数最多的任务频率为maxFreq例如A: 3 B: 3那么maxFreq 3我们先只考虑出现次数最多的任务。假设任务A出现 4 次冷却时间n 2A _ _ A _ _ A _ _ A可以发现前maxFreq - 1个最高频任务会形成若干个完整分组每个分组长度为n 1最后一组只需要放最高频任务本身不需要强制补满冷却间隔。因此基础结构是(maxFreq - 1) * (n 1)最后还要加上最后一组最高频任务的数量。五、为什么要考虑 maxCount如果只有一个最高频任务例如A: 4 B: 2 C: 1那么最高频任务只有A一个。但如果有多个任务都达到了最高频率例如A: 3 B: 3此时最后一组不只是一个A而是A B所以还需要统计maxCount 出现次数等于 maxFreq 的任务种类数最终由最高频任务决定的最短框架长度为(maxFreq - 1) * (n 1) maxCount六、为什么最终答案要和 tasks.size() 取最大值这是本题最容易误解的地方。公式(maxFreq - 1) * (n 1) maxCount表示由最高频任务构造出的最小时间框架。但是如果其他任务数量足够多它们可以完全填满冷却间隔甚至让 CPU 从头到尾不需要 idle。例如tasks [A,C,A,B,D,B] n 1频率为A: 2 B: 2 C: 1 D: 1其中maxFreq 2 maxCount 2公式结果为(maxFreq - 1) * (n 1) maxCount (2 - 1) * (1 1) 2 4但是任务总数是6CPU 至少要执行 6 个任务所以最短时间不可能小于 6。因此最终答案是max(tasks.size(), (maxFreq - 1) * (n 1) maxCount)七、公式推导总结设maxFreq 出现次数最多的任务频率 maxCount 出现次数等于 maxFreq 的任务种类数 total 任务总数那么答案为max(total, (maxFreq - 1) * (n 1) maxCount)含义如下(maxFreq - 1) 表示最高频任务之间形成的间隔段数量。 (n 1) 表示每一段至少包含一个最高频任务和 n 个冷却位置。 maxCount 表示最后一组中所有最高频任务的数量。 tasks.size() 表示所有任务本身至少需要消耗的时间。八、C 代码实现#include iostream #include vector #include algorithm using namespace std; class Solution { public: int leastInterval(vectorchar tasks, int n) { vectorint freq(26, 0); // 统计每种任务出现次数 for (char task : tasks) { freq[task - A]; } // 找到最高频率 int maxFreq 0; for (int count : freq) { maxFreq max(maxFreq, count); } // 统计有多少种任务达到了最高频率 int maxCount 0; for (int count : freq) { if (count maxFreq) { maxCount; } } // 根据公式计算最短时间 int frameLength (maxFreq - 1) * (n 1) maxCount; // 最终答案不能小于任务总数 return max((int)tasks.size(), frameLength); } };九、代码逐行解析1. 统计任务频率vectorint freq(26, 0); for (char task : tasks) { freq[task - A]; }由于题目说明任务只包含大写英文字母A到Z所以可以使用长度为 26 的数组统计频率。例如tasks [A,A,A,B,B,B]统计结果为A: 3 B: 32. 找到最高频任务数量int maxFreq 0; for (int count : freq) { maxFreq max(maxFreq, count); }maxFreq表示出现次数最多的任务出现了几次。例如A: 3 B: 3则maxFreq 33. 统计最高频任务种类数int maxCount 0; for (int count : freq) { if (count maxFreq) { maxCount; } }如果有多个任务出现次数都等于maxFreq它们都需要放在最后一组中。例如A: 3 B: 3则maxCount 2如果是A: 4 B: 2 C: 1则maxCount 14. 计算框架长度int frameLength (maxFreq - 1) * (n 1) maxCount;这个公式是本题的核心。以tasks [A,A,A,B,B,B] n 2为例maxFreq 3 maxCount 2代入公式(3 - 1) * (2 1) 2 2 * 3 2 8对应安排A B idle A B idle A B5. 与任务总数取最大值return max((int)tasks.size(), frameLength);如果任务种类足够多可以填满所有冷却间隔那么 CPU 不需要 idle。此时答案就是任务总数。例如tasks [A,B,C,D,E,F] n 2虽然有冷却限制但每个任务只出现一次不存在相同任务冲突。答案就是6十、用示例验证公式示例一tasks [A,A,A,B,B,B] n 2频率A: 3 B: 3所以maxFreq 3 maxCount 2 tasks.size() 6公式(maxFreq - 1) * (n 1) maxCount (3 - 1) * (2 1) 2 8最终答案max(6, 8) 8示例二tasks [A,C,A,B,D,B] n 1频率A: 2 B: 2 C: 1 D: 1所以maxFreq 2 maxCount 2 tasks.size() 6公式(2 - 1) * (1 1) 2 4最终答案max(6, 4) 6示例三tasks [A,A,A,B,B,B] n 3频率A: 3 B: 3所以maxFreq 3 maxCount 2 tasks.size() 6公式(3 - 1) * (3 1) 2 10最终答案max(6, 10) 10对应安排A B idle idle A B idle idle A B十一、另一种理解空槽填充法我们也可以从“空槽”的角度理解这道题。假设最高频任务是A出现了 4 次n 2A _ _ A _ _ A _ _ A一共有maxFreq - 1 3个间隔段。每个间隔段至少需要n 2个位置。所以初始空槽数量为(maxFreq - 1) * n然后用其他任务去填这些空槽。如果其他任务不够填就需要idle。如果其他任务足够多则不需要idle。不过在实际写代码时使用前面的公式更加简洁。十二、为什么贪心是正确的本题的贪心核心是优先考虑出现次数最多的任务因为它们对冷却时间的约束最强。出现次数最多的任务如果不能合理分散就一定会产生 idle。因此先将最高频任务按照冷却时间分布开再把其他任务填入间隔是最优策略。换句话说最终时间的下界由两个因素共同决定 1. 所有任务数量 tasks.size() 2. 最高频任务形成的冷却框架所以答案必须是这两者中的较大值。十三、复杂度分析时间复杂度由于任务只有大写字母A到Z频率数组长度固定为 26。统计任务需要遍历整个tasks数组。所以时间复杂度为O(m)其中m是任务总数。空间复杂度使用了一个长度为 26 的数组。因此空间复杂度为O(1)因为 26 是常数。十四、常见错误总结错误一只考虑最高频任务没有考虑并列最高频任务错误思路(maxFreq - 1) * (n 1) 1这个公式只适用于最高频任务只有一种的情况。如果A: 3 B: 3最后一组应该是A B所以要加的是maxCount不是固定加 1。正确写法(maxFreq - 1) * (n 1) maxCount错误二忘记和任务总数取最大值例如tasks [A,C,A,B,D,B] n 1如果只用公式(2 - 1) * (1 1) 2 4会得到错误答案 4。但是任务一共有 6 个至少需要 6 个时间单位。正确答案应该是max(6, 4) 6错误三试图直接模拟但没有正确处理冷却时间模拟法也可以做但需要维护任务剩余次数 任务冷却时间 当前时间 优先选择策略代码复杂度更高也更容易出错。本题更推荐使用数学贪心公式。十五、模拟法简要说明如果不使用公式也可以使用优先队列模拟。大致思路是用最大堆保存剩余次数最多的任务每一轮最多执行n 1个不同任务执行后如果任务还有剩余次数则重新放回堆中如果堆为空说明任务全部执行完如果一轮没填满且任务没结束则需要补 idle。这种方法更接近真实 CPU 调度过程但代码比公式法更长。十六、模拟法 C 代码#include iostream #include vector #include queue using namespace std; class Solution { public: int leastInterval(vectorchar tasks, int n) { vectorint freq(26, 0); for (char task : tasks) { freq[task - A]; } priority_queueint pq; for (int count : freq) { if (count 0) { pq.push(count); } } int time 0; while (!pq.empty()) { vectorint temp; int cycle n 1; for (int i 0; i cycle; i) { if (!pq.empty()) { int count pq.top(); pq.pop(); count--; if (count 0) { temp.push_back(count); } } time; if (pq.empty() temp.empty()) { break; } } for (int count : temp) { pq.push(count); } } return time; } };十七、公式法与模拟法对比方法思路时间复杂度空间复杂度推荐程度公式法根据最高频任务构造最短框架O(m)O(1)最推荐最大堆模拟法模拟每一轮任务调度O(m log 26)O(1)适合理解暴力枚举调度逐时间尝试任务较高较高不推荐其中m是任务数量。由于任务种类最多只有 26 种所以log 26可以视为常数。十八、总结LeetCode 621「任务调度器」是一道典型的贪心题。它的关键不在于真正模拟 CPU而在于分析哪些任务最容易造成冷却冲突答案是出现次数最多的任务因此我们只需要统计任务频率并找出maxFreq 最高频任务的出现次数 maxCount 达到最高频率的任务种类数最终答案为max((int)tasks.size(), (maxFreq - 1) * (n 1) maxCount)这道题的核心思想可以概括为最高频任务决定冷却框架 其他任务尽量填充空位 如果填不满就产生 idle 如果填得满答案就是任务总数因此本题最优解是贪心 频率统计 数学公式时间复杂度为O(m)空间复杂度为O(1)其中m是任务总数。