1.题目
题目地址(621. 任务调度器 - 力扣(LeetCode))
https://leetcode.cn/problems/task-scheduler/
题目描述
给你一个用字符数组 tasks
表示的 CPU 需要执行的任务列表,用字母 A 到 Z 表示,以及一个冷却时间 n
。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成,但有一个限制:两个 相同种类 的任务之间必须有长度为 n
的冷却时间。
返回完成所有任务所需要的 最短时间间隔 。
示例 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 <= tasks.length <= 104
tasks[i]
是大写英文字母0 <= n <= 100
2.题解
2.1 贪心算法 + 优先级队列
思路
这题的关键思路是我们需要明白具体的贪心策略:
当处于某一个时间点,这里有若干个未被冷却的任务等待执行,我们应该优先执行那些剩余次数较多的任务
因为其余剩余次数较少的任务,我们可以穿插到其他的时间间隔进行执行,因为剩余次数少,需要插空的位置少,更容易完成,
而那些剩余次数多的任务,如果放到后面执行,可能就会面对只剩下这类任务的情况,我们执行一个该类任务,必须等待一整个时间间隔n什么都不能做
所以我们的贪心策略:优先执行当前未处于冷却状态,且剩余执行次数较多的任务
后面一个比较好解决,使用优先级队列(大根堆)即可解决,我们如何解决前面一个限制呢?
我们发现我们如果是以一个冷却周期n来划分任务执行,那么假设这个冷却周期我执行了若干任务,并执行一个从优先级队列中排除一个;
并在这个冷却周期完毕后(指第一个任务,中间其他任务尚未完成冷却),将所有本周期执行过的,被排除的任务全部装回优先级队列,并执行下一个周期;
我们可能有一个疑问,此时优先级队列中不是所有任务都冷却了(上一个周期执行的后几个任务都未冷却),我们直接放回开启新周期可以吗?
答案是可以的,在下一个周期中,我们还是按,有这么几种可能:
1.这里执行的任务上个冷却周期我没执行过(由于上一周期任务执行,部分任务执行次数减少后小于该任务,导致该任务优先级上升),那么自然没有冷却问题的
(关键!!!)2.这里执行的任务上个冷却周期我执行过(但是根据上一周期中优先级高于你的任务,你们的剩余次数同时-1,其实这一周期还是按次序还是排在你前面的,等他执行完,你也就冷却好了!!!)
所以我们就可以采用一个冷却周期一轮回的方式来解决这个问题,一个轮回中:
1.执行n+1个任务(自己执行的一次 + 冷却时间的n次),并排除优先级队列
2.执行完毕后,将这些任务放回优先级队列
3.更新总执行时间
代码
- 语言支持:C++
C++ Code:
class Solution {
public:
int leastInterval(std::vector<char>& tasks, int n) {
// 统计任务出现频率
unordered_map<char, int> taskFreq;
for(char ch : tasks){
if(taskFreq.count(ch)){
taskFreq[ch]++;
}else{
taskFreq.emplace(ch, 1);
}
}
// 使用优先级队列-维护剩余次数从大到小排列(大根堆)
priority_queue<int> maxheap;
for(auto p : taskFreq){
maxheap.push(p.second);
}
int ans = 0;
// 开始时间流动,每次循环一个时间冷却时间
while(!maxheap.empty()){
vector<int> temp;
// 执行当前剩余次数最多的任务(一个周期:自己执行的一个间隔 + 冷却室家n)
for(int i = 0; i < n + 1; i++){
if(!maxheap.empty()){
temp.push_back(maxheap.top() - 1);
maxheap.pop();
}
}
// 执行完一轮后,将未完成的任务放回优先级队列中
for(int tmp : temp){
if(tmp > 0){
maxheap.push(tmp);
}
}
// 更新完成当前任务总的时间间隔
// 如果栈为空,说明最后temp中的值均为0,所有任务执行完毕,加上这一部分即可
if(maxheap.empty()){
ans += temp.size();
}else{
ans += n + 1;
}
}
return ans;
}
};
复杂度分析
- 时间复杂度:'o(w* log K),其中'N 是任务的总数量,'K 是任务种类的数量。
对于每个任务操作,堆的操作(插入和删除)是“o(log K)”的。 - 空间复杂度:‘’o(k)”,主要用于存储任务频率的哈希表和优先级队列。