[路飞]_leetcode-621-任务调度器

简介: leetcode-621-任务调度器

网络异常,图片无法展示
|


[题目地址][B站地址]


给你一个用字符数组 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 时,无需间隔,那么最短时间就是任务数量,即 stasks.length


如果 n>0,则需要首先找到出现次数最多的一种任务,将其按间隔排好,然后将其他任务合理的插入间隔


这里大家不要尝试着去进行整个过程,虽然这样也能解决本题,但是费时费力


这里我们只需要判断如下情况,而不需要真的进行整个插入过程即可完成解题


这里会出现以下三种情况


  1. 剩余任务数量比间隔多,说明剩余任务的种类的肯定要比间隔多,此时,将任务适当排列即可,最短时间是任务数量


示例:


tasks = ["A","A","A","A","A","A","B","B","B","B","C","C","C","C","D","E","E","F","F"],
n = 2
// 一种排列后的结果
A,B,C,A,B,C,A,B,C,A,B,C,A,E,F,A,E,F,D
复制代码


  1. 如果剩余任务的数量比间隔少,此时间隔无法填满,此时最短时间是出现次数最多任务的执行用时


示例:


tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], 
n = 2
// 一种排列后的结果
A,B,C,A,D,E,A,F,G,A,,,A,,,A
复制代码


  1. 要注意的是可能次数最多的任务有多个,这个时候的最短用时等于出现次数最多的任务执行用时加上出现次数最多的任务数量-1


示例:


["A","A","A","B","B","B"], 
n = 2
// 一种排列后的结果
A,B,,A,B,,A,B
复制代码


所以本题只需要找到出现次数最多的任务的次数,以及是否有多个出现次数最多的任务,求得它们的执行用时


与任务数量之间相比,取最大值返回即可


代码如下:


var leastInterval = function(tasks, n) {
 const length = tasks.length;
 // 间隔为零,直接返回任务长度
 if(n===0) return length;
 // 记录每种任务执行次数
 const map = new Map();
 for(let i = 0;i<length;i++){
   const item = tasks[i]
   if(map.has(item)){
     map.set(item,map.get(item)+1)
   }else{
     map.set(item,1)
   }
 }
 // 获取执行次数最多的任务的次数以及相同次数的任务的数量
 let max = 0,maxNum = 0;
 map.forEach(item => {
   if(item>max){
     max = item;
     maxNum = 1
   }else if(item === max){
     maxNum++
   }
 })
 // 返回执行次数最多任务执行用时与任务数量的最大值
 return Math.max((n+1)*(max-1)+maxNum,length)
};
复制代码


至此我们就完成了 leetcode-621-任务调度器


如有任何问题或建议,欢迎留言讨论!

相关文章
|
6月前
|
调度
leetcode-621:任务调度器
leetcode-621:任务调度器
51 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
46 4
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
107 2
|
9天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
11 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
54 7
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
25 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
50 5