力扣题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 -> (待命) -> (待命) -> A

1.

class Solution {    public int leastInterval(char[] tasks, int n) {        Map
freq = 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) {        Map
freq = 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Git和GitHub
下一篇:力扣题617合并二叉树

发表评论

最新留言

不错!
[***.144.177.141]2024年03月12日 11时54分49秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

读文件程序一行的函数c语言,c fgets()函数 读取文件时位置会自动移动下一行吗?该如何处理... 2019-04-21
老船履带工具使用方法_电流表工具的正确使用方法 2019-04-21
中矩阵运算_VS 2017中添加Eigen库-c++矩阵运算工具 2019-04-21
传递list对象作为参数_程序员你如何检查参数的合法性? 2019-04-21
打开stp选择哪个许可证_全省首张“广播电视节目制作经营许可证”电子证照上线“皖事通”... 2019-04-21
互联网和大数据是什么意思_数据化和互联网行业 互联网大数据什么意思 2019-04-21
发那科机器人没有码垛指令_FANUC 机器人码垛编程详细讲解 2019-04-21
python播放器模块_如何在单独的模块中调用播放器 2019-04-21
java吕局部峰值_JVM的运行数据区划分 2019-04-21
时间复杂度为on的排序算法_算法基础--时间复杂度,三个常规O(N?)的排序算法(冒泡、选择、插入)... 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
mysql 5.7 io 性能 aio_(转)【干货】MySQL 5.7 多实例(多进程)配置教程 2019-04-21
sql ssas mdx 导出结果_DAX中按列排序的另一种结果 2019-04-21
iphone mysql 客户端_如何实现iphone端通过soap访问mysql数据库 2019-04-21