AlgoPressAppearance
题目描述
https://leetcode.cn/problems/task-scheduler
给你一个用字符数组 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 <= 104 tasks[i] 是大写英文字母 n 的取值范围为 [0, 100]
思路
CPU一个周期里面不能执行同一个task，所以我们要尽量保留足够多种类的task。 将task累计排序，每次从最多的task取一个执行，执行的周期之内把当前task缓存，第二次就需要取其他task。 当所以task在这个周期都是缓存状态，则空转一轮，即无法获取task
当下一个周期开始，把缓存清空重新计数。
task 使用 hash 表统一管理起来，每次遍历hash表取出个数最多的task开始运行。
参考代码
csharp
public class Solution {
public int LeastInterval(char[] tasks, int n) {
//尽量处理不同的任务
//每个周期用完，则尽量从任务最多的开始执行
int time = 0;
//使用hash表缓存任务
Dictionary<char,int> dict = new Dictionary<char,int>();
for(int i=0; i<tasks.Length; i++){
if(!dict.ContainsKey(tasks[i])){
dict.Add(tasks[i],1);
}
else{
dict[tasks[i]]++;
}
}
Dictionary<char,int> curTask = new Dictionary<char,int>();
//输出任务
// Console.WriteLine("输出总任务");
// foreach(char c in dict.Keys){
// Console.WriteLine("task:{0}={1}",c,dict[c]);
// }
while(dict.Count > 0){
curTask.Clear();
for(int i=0;i<=n;i++){
//Console.WriteLine("===第 {0} 轮===",i);
if(dict.Count > 0 ){
time++;
//取得一个Task
char c = GetTask(dict,curTask);
if(c != ' '){
//Console.WriteLine("添加 Task {0} 到 curTask",c);
curTask.Add(c,1);
}
//Console.WriteLine("执行Task : {0}",c);
}
}
}
return time;
}
private char GetTask(Dictionary<char,int> dict, Dictionary<char,int> curTask){
// Console.WriteLine("输出Task总任务");
// foreach(char c in dict.Keys){
// Console.WriteLine("task:{0}={1}",c,dict[c]);
// }
// Console.WriteLine("输出当前任务");
// foreach(char c in curTask.Keys){
// Console.WriteLine("curTask:{0}={1}",c,curTask[c]);
// }
//得到次数最多的task，且没有执行过的task
int maxCount = 0;
char task = ' ';
foreach(char c in dict.Keys){
if(!curTask.ContainsKey(c)){
maxCount = Math.Max(dict[c],maxCount);
}
}
//Console.WriteLine("maxCount:{0}",maxCount);
foreach(char c in dict.Keys){
if(!curTask.ContainsKey(c)){
if(dict[c] == maxCount){
task = c;
dict[c]--;
if(dict[c] == 0){
dict.Remove(c);
}
break;
}
}
}
return task;
}
}
复习：20220713
参考题解 : https://leetcode.cn/problems/task-scheduler/solution/tong-zi-by-popopop/
主要方法是算出最小执行时间。 根据冷却时间 n ，最多任务数 count 可以知道 (count-1) * (n+1) + 1 就是最小执行时间，注意是最后一排因为不需要冷却，所以+1就当前task需要执行的1个时间单位。 然后遍历任务列表，将所有执行次数和A相等的task找出来，次数都+1
csharp
public class Solution {
public int LeastInterval(char[] tasks, int n) {
//找出最大的执行次数
Dictionary<char,int> dict = new Dictionary<char,int>();
int maxCount = 0;
for(int i=0; i<tasks.Length; i++){
dict[tasks[i]] = dict.ContainsKey(tasks[i]) ? dict[tasks[i]]+1 : 1;
}
maxCount = dict.Values.Max();
//根据等待时间创建n+1个桶,计算最小执行时间
int minLength = (n+1) * (maxCount-1) ;
foreach(char c in dict.Keys){
if(dict[c] == maxCount){
minLength++;
}
}
//返回
return Math.Max(tasks.Length,minLength);
}
}