任务调度器
解题思路：
-
第一种情况：
- 设计桶的大小为 n+1，则相同的任务恰好不能放入同一个桶（一行为一个桶），最密也只能放入相邻的桶；
- 对于重复的任务，只能将每个都放入不同的桶中，因此桶的个数就是重复次数最多的任务的个数；
- 一个桶不管是否放满，其占用的时间均为 n+1，这是因为后面桶里的任务需要等待冷却时间；
- 最后一个桶是个特例，由于其后没有其他任务需等待，所以占用的时间为桶中的任务个数；
- 最终我们得到：总排队时间 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数
-
第二种情况：
- 当任务重复率很低时，计算得到的桶个数很少；
- 但由于任务很多，可能出现桶不够用的情况，此时可以假想原来的桶被加长了，且所有的桶均装满，因此任务的总等待时间即为任务的总个数；
- 则对第一种情况和第二种情况的结果取最大值即可；
图解：
复杂度：
-
时间复杂度：O(n)；
-
空间复杂度：O(1)；
代码实现：
var leastInterval = function (tasks, n) {
let arr = new Array(26).fill(0)
for (let t of tasks) {
//统计各个字母出现的次数
arr[t.charCodeAt() - 'A'.charCodeAt()]++
}
// 找到最大次数
let max = Math.max(...arr)
// 计算前n-1行n的间隔的时间大小
let ret = (max - 1) * (n + 1)
// 获取最后一桶的任务数
for (let i = 0; i < 26; i++) {
if (arr[i] === max) {
ret++
}
}
// 取最大值
return Math.max(ret, tasks.length)
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
1021.删除最外层的括号
上一篇
评论
