任务调度器
- 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 <= 1 0 4 10^4 104
- tasks[i] 是大写英文字母
- n 的取值范围为 [0, 100]
算法实现
1 ）方案 1文章来源：https://www.toymoban.com/news/detail-433660.html
function leastInterval(tasks: string[], n: number): number {
let result = '' // 最终队列执行的结果
const dict = {} // 对归类进行存储
tasks.forEach((item) => {
dict[item] ? (dict[item] ++) : (dict[item] = 1)
})
while(true) {
// 任务清单
const keys = Object.keys(dict)
// 任务处理完毕跳出
if (!keys.length) {
break
}
// 正常处理过程
let tmp = [] // 用于存储 1 + n个任务单元
for (let i = 0; i <= n; i++) {
let max:number = 0 // 找到最大的任务
let key:string
let pos:number
// 遍历任务清单
keys.forEach((item, idx) => {
// 当前任务数量大于max
if (dict[item] > max) {
max = dict[item] // 存储更新max
key = item // 存储更新当前任务
pos = idx // 存储更新当前任务下标索引，用于后续的删除操作
}
})
// 没有匹配到key, 直接跳出此次循环
if (!key) {
break
}
// 找到了key
tmp.push(key) // 临时队列添加当前的key
keys.splice(pos, 1) // 将当前key从任务队列中删除
dict[key] -- // 更新key的长度，已消费完成，删除来更新剩余个数
// 当全部消费完成，移除当前的任务
if (dict[key] < 1) {
delete dict[key]
}
}
result += tmp.join('').padEnd(n + 1, '-') // 如果不全，补充冷却时间
}
// 边界的处理, 最后不要出现冷却时间
result = result.replace(/-+$/, '')
return result.length
}
- 关键需求分析：
- 两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间
- 因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
- 要求，完成所有任务的最短时间
- 从上面的描述和示例中可见
- 队列中有A,B,C,…, 现在开启了一个任务
- 如果当前开启了A任务，那接下来n个的任务中不能有A了
- 如果其他任务不够n的长度，那么要冷却等待
- 只要现在队列中还有任务，我就要处理任务本身和n个任务冷却时间的 n+1 的任务，
- 也就是从队列中取出这些任务来存放，求最短的存放时间
- 如何做到最短，考虑使用最多的任务优先处理，尽量不会有剩余，交叉着来
- 少的来进行插缝作业，这样即保证少的任务使用了
- 又保证多的任务不会用冷却时间处理来占用更多资源
- 这个算法，在实现上效率不高
2 ）方案 2文章来源地址https://www.toymoban.com/news/detail-433660.html
function leastInterval(tasks: string[], n: number): number {
// 初始化一个矩阵，用于存储给定任务的数量的字典
const cnts = Array(26).fill(0);
for(const c of tasks) {
cnts[c.charCodeAt(0) - 'A'.charCodeAt(0)]++;
}
// 统计出任务中对多的数量
let max = 0, tot = 0;
for (let i = 0; i < 26; i++) {
max = Math.max(max, cnts[i]);
}
// 更新tot变量的值，用于统计具有最多执行次数的任务数量
for (let i = 0; i < 26; i++) {
tot += max === cnts[i] ? 1 : 0;
}
// 这里是最核心的算法
return Math.max(tasks.length, (n + 1) * (max - 1) + tot)
};
- 这是官方示例，效率很高
- 这里用到charCodeAt() 方法可返回指定位置的字符的 Unicode 编码
- 后续有时间再研究下：https://leetcode.cn/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode-solution-ur9w/ 中的方法二：构造
到了这里，关于数据结构与算法之队列: Leetcode 621. 任务调度器 (Typescript版)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
