621. 任务调度器
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 ：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
提示：
任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/task-scheduler
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
基本思路：首先，是使用哈希表存储每个任务的个数，当任务只需要1轮时，即每个任务的个数都是1次，结果就是任务数;当需要进行多轮时，决定轮数的是同类任务个数最多的，同时每轮的时间大于等于n+1,具体要分两种情况讨论：
- 假设，同类任务个数最多的为A,其个数为s,若有多个个数为s的同类任务，其总数为k,总轮数rounds=s,每轮的时间t>=n+1,最后一轮时间cnt=k
- 除去最后一轮，若其他各轮的时间都大于等于n+1，此时，由于每轮之间不需要冷却时间，所以结果就是任务总数len>（n+1)*(s-1)+cnt
- 除去最后一轮，若其他轮的时间存在小于n+1,此时每轮的时间都是n+1,总时间=（n+1)*(s-1)+cnt>len;
也可以用桶来演示，一共s轮，代表有s个桶，其中，每个桶都大于等于n+1(包括冷却)，装桶规则，在每个桶都大于n+1之前，尽量将每个桶都装满（也就是说每一轮中，不必将所有不同任务都过一遍），每个桶装大于n+1后，总耗时就是任务总数
int leastInterval(vector<char>& tasks, int n) {
vector<int> dict(26,0);
int res=0,cnt=1,len=tasks.size();
for(auto &ch:tasks){
dict[ch-'A']++;
}
sort(dict.rbegin(),dict.rend()); //逆序
//sort(dict.begin(),dict.end(),[](int& x,int&y){return x>y;});
while(cnt<dict.size()&&dict[cnt]==dict[0]) //dict[0],桶的个数
cnt++; //最后一个桶的大小
res=max(len,cnt+(n+1)*(dict[0]-1));
return res;
}基本思路： 基于上述思路，也可以使用排序的方法，类似与优先队列，每一轮按照同类任务数目的多少制定优先级。
int leastInterval(vector<char>& tasks, int n) {
vector<int> dict(26,0);
int cnt=0;
for(auto &ch:tasks){
dict[ch-'A']++;
}
sort(dict.rbegin(),dict.rend()); //逆序
//sort(dict.begin(),dict.end(),[](int& x,int&y){return x>y;});
while(dict[0]>0){
int i=0;
while(i<=n){
if(dict[0]==0)
break;
if(i<26&&dict[i]>0){
dict[i]--;
}
i++;
cnt++;
}
sort(dict.rbegin(),dict.rend());
}
return cnt;
}