【贪心-3】621.任务调度器

题目描述给你一个用字符数组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 个间隔分割。这导致重复执行这些任务的间隔当中有两次待命状态。解题思路方法一贪心核心思路出现次数最多的任务决定了总时间的下限。假设出现次数最多的任务为 A出现maxCount次A _ _ A _ _ AA 之间有maxCount - 1个间隔每个间隔长度至少为n总框架长度 (maxCount - 1) × (n 1) 1最后还要加上有多少个任务和 A 出现次数相同maxCountTasks它们需要排在最后一个 A 的后面。最终公式result max(总任务数, (maxCount - 1) × (n 1) maxCountTasks)为什么取 max如果任务很多冷却时间被其他任务填满不需要待命总时间就是任务总数如果任务少冷却时间填不满需要待命总时间由公式计算具体过程示例tasks [A,A,A,B,B,B], n 2A 出现 3 次B 出现 3 次 maxCount 3, maxCountTasks 2A 和 B 都是 3 次 框架: A _ _ A _ _ A 公式: (3-1) × (21) 2 6 2 8 总任务数 6 result max(6, 8) 8 ✅tasks [A,A,A,B,B,B,C,C,D,D], n 2A 出现 3 次B 出现 3 次 maxCount 3, maxCountTasks 2A 和 B 公式: (3-1) × (21) 2 8 总任务数 10 result max(10, 8) 10 ✅代码实现class Solution { public: int leastInterval(vectorchar tasks, int n) { // 统计每个任务的出现次数 vectorint count(26, 0); for (char task : tasks) { count[task - A]; } // 找最大出现次数 int maxCount 0; for (int c : count) { maxCount max(maxCount, c); } // 统计有多少个任务出现次数等于 maxCount int maxCountTasks 0; for (int c : count) { if (c maxCount) maxCountTasks; } // 公式计算 int formula (maxCount - 1) * (n 1) maxCountTasks; return max((int)tasks.size(), formula); } };复杂度分析维度复杂度说明时间复杂度O(n)遍历 tasks 一次 遍历 26 个字母空间复杂度O(1)固定大小 26 的数组n 是任务数量。关键细节1. 为什么公式是(maxCount - 1) × (n 1) maxCountTasksmaxCount - 1最大出现次数任务之间的间隔数n 1每个间隔加上任务本身占用的位置 maxCountTasks最后一个间隔后面还有maxCountTasks个任务2. 为什么取max(tasks.size(), formula)如果任务很多冷却时间被填满总时间 任务总数如果任务少需要待命总时间 公式计算值3. 为什么不用模拟模拟需要 O(总时间) 时间而总时间可能很大。公式法 O(n) 更高效。方法二优先队列思路用大根堆维护剩余任务数每轮取前 n1 个任务执行。代码实现class Solution { public: int leastInterval(vectorchar tasks, int n) { vectorint count(26, 0); for (char task : tasks) count[task - A]; priority_queueint pq; for (int c : count) { if (c 0) pq.push(c); } int time 0; while (!pq.empty()) { vectorint temp; int cycle n 1; while (cycle 0 !pq.empty()) { int cnt pq.top(); pq.pop(); if (cnt 1) temp.push_back(cnt - 1); cycle--; time; } for (int cnt : temp) pq.push(cnt); // 如果堆不为空说明还需要待命 if (!pq.empty()) { time cycle; // 待命时间 } } return time; } };复杂度时间 O(总时间 × log 26)空间 O(26)缺点总时间可能很大不如公式法高效。两种方法对比方法时间复杂度空间复杂度推荐度贪心 数学公式O(n)O(1)⭐⭐⭐⭐⭐优先队列模拟O(总时间 × log 26)O(26)⭐⭐⭐总结要点说明核心思想最大出现次数决定下限取公式和任务总数的较大值关键公式(maxCount - 1) × (n 1) maxCountTasks时间复杂度O(n)空间复杂度O(1)