leetcode621：任务调度器
先看问题：
给定一个用字符数组表示的 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]。
解答思路
首先看到“大写的A-Z”时，我就想到应该可以用大小为26的数组来充当辅助数组，但之后却没有一个良好完整的思路，纠结无果后，去网上找了题解来看，这里来记录一下这道题，以供自己日后温习。
以 [“A”,“A”,“A”,“A”,“B”,“B”,“B”,“B”,“C”,“C”,“C”,“D”,“D”,“E”]，n = 2，为例来进行说明。
首先用26大小数组来确定每个任务的数量，然后将数组进行排序，将数量最大的排到最后。由于任务是交替执行的，数量最多的任务必然应该安排到每个n的节点上以求达到最短时间，如图（其中“#”代表除A以外的其他字符）：
| A | # | # | A | # | # | A | # | # | A | # | … |
|---|
这时可以看到ans至少等于（A的数量-1）*（n + 1）+ 1，其它数量小于等于A的字符就可以被安插在“#”的位置。这时数量等于A的字符必然会占到最后一个A后面“#”的位置，如下图的B，这时ans的数量就要加一：
| A | C | # | A | C | # | A | C | # | A | C | … |
|---|
代码：
class Solution {
public int leastInterval(char[] tasks, int n) {
int len = tasks.length;
if(len < 1 || n < 0){
return 0;
}
int[] nums = new int[26];
int i = 0;
//得到每个字符的数量后再排序
while(i < len){
nums[tasks[i++] - 65]++;
}
Arrays.sort(nums);
//res的最小值
int res = (nums[25] - 1) * (n + 1);
i = 25;
while(i >= 0 && nums[i] == nums[25]){
//若最多数量的字符有多个 则res相应地+1
res++;
i--;
}
//得到的结果为res与数组长度len之间最大值
return res > len ? res : len;
}
}