力扣题621任务调度器
发布日期:2022-03-04 11:48:21
浏览次数:4
分类:技术文章
本文共 2701 字,大约阅读时间需要 9 分钟。
给你一个用字符数组 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 -> (待命) -> (待命) -> A1.
class Solution { public int leastInterval(char[] tasks, int n) { Mapfreq = new HashMap<>();//存储每个字符出现的次数 for (char task : tasks) { freq.put(task,freq.getOrDefault(task,0) + 1); } int m = freq.size();//任务类型总数 List nextValid = new ArrayList<>();//存储每种任务的最早可以执行的时间 List rest = new ArrayList<>();//存储每种任务的剩余次数 Set > entrySet = freq.entrySet(); for (Map.Entry entry : entrySet) { int value = entry.getValue(); nextValid.add(1);//初始化为1,每种任务都可以在一开始就执行 rest.add(value);//初始化为出现的次数 } int time = 0; for (int i = 0;i < tasks.length;i++) { time++; int minNextValid = Integer.MAX_VALUE; for (int j = 0;j < m;j++) { if (rest.get(j) != 0) {//找到每个还有剩余次数的任务的最早执行时间 minNextValid = Math.min(nextValid.get(j),minNextValid); } } time = Math.max(time,minNextValid);//快速更新time,避免等待期间不必要的遍历 //找到可以执行的并且剩余次数最多的任务 int best = -1; for (int j = 0;j < m;j++) { if (rest.get(j) != 0 && nextValid.get(j) <= time) { if (best == -1 || rest.get(j) > rest.get(best)) { best = j; } } } //更新刚执行过的任务的下次执行时间和剩余次数 nextValid.set(best,time + n + 1); rest.set(best,rest.get(best) - 1); } return time; }}
2.
class Solution { public int leastInterval(char[] tasks, int n) { Mapfreq = new HashMap<>(); int maxExec = 0;//单类任务的最大执行次数 for (char task : tasks) { int exec = freq.getOrDefault(task,0) + 1; freq.put(task,exec); maxExec = Math.max(maxExec,exec);//更新最大执行次数 } int maxCount = 0;//拥有最大执行次数的任务的数量 Set > entrySet = freq.entrySet(); for (Map.Entry entry : entrySet) { int value = entry.getValue(); if (value == maxExec) {//执行次数等于最大执行次数,就将任务数量加1 maxCount++; } } return Math.max(tasks.length,(maxExec - 1) * (n + 1) + maxCount); }}
题源:
转载地址:https://blog.csdn.net/xxyneymar/article/details/122318606 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年03月12日 11时54分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
老船履带工具使用方法_电流表工具的正确使用方法
2019-04-21
中矩阵运算_VS 2017中添加Eigen库-c++矩阵运算工具
2019-04-21
传递list对象作为参数_程序员你如何检查参数的合法性?
2019-04-21
互联网和大数据是什么意思_数据化和互联网行业 互联网大数据什么意思
2019-04-21
发那科机器人没有码垛指令_FANUC 机器人码垛编程详细讲解
2019-04-21
python播放器模块_如何在单独的模块中调用播放器
2019-04-21
java吕局部峰值_JVM的运行数据区划分
2019-04-21
mongodb创建数据库用户名和密码_mongodb给数据库创建用户密码
2019-04-21
.net api reference中文_.NET的关于人脸识别引擎分享(C#)
2019-04-21
10个数冒泡排序流程图_程序员必知必会的 10 个排序算法
2019-04-21
mysql存储过程需要设置_在MYSQL中使用存储过程要设置什么地方吗解决办法
2019-04-21
mysql有闪回吗_MySQL误删闪回工具
2019-04-21
mysql ndb存储引擎_mysql存储引擎memory,ndb,innodb之选择
2019-04-21
mysql 多条件查询优化_MySQL 多条件多排序查询优化
2019-04-21
sql ssas mdx 导出结果_DAX中按列排序的另一种结果
2019-04-21
iphone mysql 客户端_如何实现iphone端通过soap访问mysql数据库
2019-04-21