力扣621——任务调度器
这道题主要是找规律，优化的时候可以采用贪心算法的思想。
原题
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 1：
输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
注：
- 任务的总个数为 [1, 10000]。
- n 的取值范围为 [0, 100]。
原题url：https://leetcode-cn.com/problems/task-scheduler/
解题
找规律
这道题的思路，正向推导的话，其实就是优先排出现次数多的任务，根据间隔 n ，填充任务，直到所有任务的次数最终都减为0。
因此，我们可以用数组存储任务的总次数（因为用大写英文字母表示任务，那就代表最多只能有26种任务），排序之后，按照间隔 n ，从大到小取任务，取完后，再对数组排序，重复上述取任务的过程，直到数组的最大值为0。
接下来我们看看代码：
public class Solution {
public int leastInterval(char[] tasks, int n) {
// 将task放入数组中
int[] countArray = new int[26];
for (char task: tasks) {
countArray[task - 'A']++;
}
// 从小到大，进行排序
Arrays.sort(countArray);
// 最终耗时
int time = 0;
// 从大到小开始遍历
while (countArray[25] > 0) {
// 每次遍历前n个数
int i = 0;
while (i <= n) {
// 说明所有任务已经执行完成
if (countArray[25] == 0) {
break;
}
// 遍历
if (i < 26 && countArray[25 - i] > 0) {
countArray[25 - i]--;
}
// 耗时+1
time++;
// 更换任务
i++;
}
// 从小到大排序
Arrays.sort(countArray);
}
return time;
}
}
提交OK，但执行时间上确实不太好，只打败了47.62%的 java 执行时间，其时间复杂度为O(time)， time 代表最终的执行时间。
贪心算法
我们再来想想这道题，影响最终执行时间的，有两个因素，一个是任务中出现的最大次数，另一个就是间隔 n 了。
如果我们站在最多任务的角度，来看这个问题，假设其最大次数为 maxCount，那么该任务所需的最短执行时间为(maxCount - 1) * (n + 1) + 1，如果还有其他 i 个和 maxCount 相同次数的任务，那么需要在最终的结果上再加上 i。
那么上面求出来的就是正确答案了吗？
并不是，因为上面的最短时间，是当剩余时间片能够塞满任务数小于 maxCount 的所有任务。假设 n 很小，那么剩余任务肯定需要在任务数等于 maxCount 的那些任务执行完之后，还要继续执行。
但因为最大任务已经可以满足在间隔时间内执行完，那么出现次数小于 maxCount 的任务，肯定可以连续执行完成的，也就是不需要空闲等待时间。那么此时的最短执行时间也就是总任务数了。
接下来我们看看代码：
public class Solution {
public int leastInterval(char[] tasks, int n) {
if (tasks.length == 0 || n == 0) {
return tasks.length;
}
// 将task放入数组中
int[] countArray = new int[26];
for (char task : tasks) {
countArray[task - 'A']++;
}
// 从小到大，进行排序
Arrays.sort(countArray);
// 获取最大次数
int maxCount = countArray[25];
// 如果其他次数都比maxCount小的话，求出针对maxCount的最短时间
int result = (maxCount - 1) * (n + 1);
// 遍历countArray
for (int i = 25; i >= 0; i--) {
// 如果有和maxCount相同的，则执行时间+1
if (countArray[i] == maxCount) {
result++;
}
// 否则，直接结束
else {
break;
}
}
// 如果总任务数比理论上的最短时间长，说明任务很多，但可以把每个桶填满，因此最短时间也就是总任务数
return Math.max(result, tasks.length);
}
}
提交OK ，在所有 Java 提交中击败了100.00%的用户，确实快了很多。其时间复杂度为O(M)，M 代表总任务数。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要是找规律，优化的时候可以采用贪心算法的思想。