（贪心）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 个间隔分割。这导致重复执行这些任务的间隔当中有两次待命状态。提示1 tasks.length 10sup4/suptasks[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 个时间单位才能再次执行。所以相邻两次相同任务的执行位置至少相差n1所以得到公式(maxTimes−1)(n1)(\text{maxTimes}-1)(n1)(maxTimes−1)(n1)maxCount出现次数等于maxTimes的任务种类数。如果有多个任务都达到了最大频次它们都需要放在最终一组的末尾用来计算排程的最短长度。上述的公式只是最高频次任务最后一次出现的最早位置还没有考虑其他并列最高频次的任务。如A 3 次B 3 次C 2 次n 2则maxTimes 3; maxCount 2;A 和 B 的第三次出现都不能早于时间位置(3−1)(21)6(3-1)(21)6(3−1)(21)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 2maxTimes 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); } }