罗庄建设局网站,建设银行人力资源网站,网站demo制作工具,免费做效果图的软件621. 任务调度器 - 力扣#xff08;LeetCode#xff09; 一、题目
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行#xff0c;并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间LeetCode 一、题目
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间CPU 可以完成一个任务或者处于待命状态。
然而两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间因此至少有连续 n 个单位时间内 CPU 在执行不同的任务或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例 1
输入tasks [A,A,A,B,B,B], n 2 输出8 解释A - B - (待命) - A - B - (待命) - A - B 在本示例中两个相同类型任务之间必须间隔长度为 n 2 的冷却时间而执行一个任务只需要一个单位时间所以中间出现了待命状态。
示例 2
输入tasks [A,A,A,B,B,B], n 0 输出6 解释在这种情况下任何大小为 6 的排列都可以满足要求因为 n 0 [A,A,A,B,B,B] [A,B,A,B,A,B] [B,B,B,A,A,A] ... 诸如此类
示例 3
输入tasks [A,A,A,A,A,A,B,C,D,E,F,G], n 2 输出16 解释一种可能的解决方案是 A - B - C - A - D - E - A - F - G - A - (待命) - (待命) - A - (待命) - (待命) - A
提示
1 task.length 104tasks[i] 是大写英文字母n 的取值范围为 [0, 100]
二、代码
class Solution {public int leastInterval(char[] tasks, int n) {// 统计每一个字符的词频int[] count new int[Z 1];// 出现最多次的任务到底是出现了几次int maxCnt 0;for (int i 0; i tasks.length; i) {count[tasks[i]];maxCnt Math.max(maxCnt, count[tasks[i]]);}// 有多少种任务都出现最多次int maxNumCnt 0;for (char c A; c Z; c) {if (count[c] maxCnt) {maxNumCnt;}}// 完成全部任务需要的最短时间int ans 0;// maxNumCnt : 有多少种任务都出现最多次// maxCnt : 最多次是几次// 出现最多次的任务占用的时间(maxNumCnt * maxCnt) 产生的所有空格的时间。// maxCnt - 1:产生的间隙数 // n - maxNumCnt 1产生的每一个间隙都有多少个空格 ans maxNumCnt * maxCnt (n - maxNumCnt 1) * (maxCnt - 1);// 如果空格不足以把剩下的任务都填满就需要在每一部分的最后追加没有被填上的任务if (ans tasks.length) {// 累加剩余没有被填进去的任务数ans (tasks.length - ans);}return ans;}
}
三、解题思路
出现次数最多的任务只有一种
假设a出现次数最多a一共出现了5次
下面我们就用别的任务去补齐空格此时所有的a是达标的。紧着词频第二大的先往里填。依次执行下去最后把所有的任务都插入进去最后得到的就是耗时最小的任务调度。
