当前位置: 首页 > news >正文

【LeetCode】任务调度器 [M](贪心)

621. 任务调度器 - 力扣(LeetCode)

一、题目

给你一个用字符数组 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, 100]

二、代码

class Solution {public int leastInterval(char[] tasks, int n) {// 统计每一个字符的词频int[] count = new int['Z' + 1];// 出现最多次的任务,到底是出现了几次int maxCnt = 0;for (int i = 0; i < tasks.length; i++) {count[tasks[i]]++;maxCnt = Math.max(maxCnt, count[tasks[i]]);}// 有多少种任务,都出现最多次int maxNumCnt = 0;for (char c = 'A'; c < 'Z'; c++) {if (count[c] == maxCnt) {maxNumCnt++;}}// 完成全部任务需要的最短时间int ans = 0;// maxNumCnt : 有多少种任务,都出现最多次// maxCnt : 最多次,是几次?// 出现最多次的任务占用的时间(maxNumCnt * maxCnt) + 产生的所有空格的时间。// maxCnt - 1:产生的间隙数 // n - maxNumCnt + 1:产生的每一个间隙都有多少个空格     ans = maxNumCnt * maxCnt + (n - maxNumCnt + 1) * (maxCnt - 1);// 如果空格不足以把剩下的任务都填满,就需要在每一部分的最后追加没有被填上的任务if (ans < tasks.length) {// 累加剩余没有被填进去的任务数ans += (tasks.length - ans);}return ans;}
}

三、解题思路 

出现次数最多的任务只有一种

假设a出现次数最多,a一共出现了5次

下面我们就用别的任务去补齐空格,此时所有的a是达标的。紧着词频第二大的先往里填。依次执行下去,最后把所有的任务都插入进去,最后得到的就是耗时最小的任务调度。

相关文章:

【LeetCode】任务调度器 [M](贪心)

621. 任务调度器 - 力扣&#xff08;LeetCode&#xff09; 一、题目 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行&#xff0c;并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间&…...

Spring代理模式——静态代理和动态代理

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

Anaconda和PyCharm的一些安装问题和命令

今天更新了Windows上的Anaconda到2.3.2&#xff0c;PyCharm到2022.3。 ——发现是纯纯的犯贱orz。出了一堆问题。在这里记录一下供后来者参考。 Anaconda安装 将.\anaconda3\Scripts 和.\anaconda3\Library\bin添加到系统环境变量中。 新建环境的目录在.\anaconda3\envs下 N…...

sql优化建议

对查询进行优化&#xff0c;应尽量避免全表扫描&#xff0c;首先应考虑在 where 及 order by 涉及的列上建立索引。 应尽量避免在 where 子句中使用!或<>操作符&#xff0c;否则将引擎放弃使用索引而进行全表扫描。 应尽量避免在 where 子句中对字段进行 null 值判断&a…...

google hacker语句

哎&#xff0c;我就是沾边&#xff0c;就是不打实战(&#xffe3;o&#xffe3;) . z Z 文章目录前言一、什么是谷歌Docker&#xff1f;二、受欢迎的谷歌docker语句谷歌docker的例子日志文件易受攻击的 Web 服务器打开 FTP 服务器SSH私钥电子邮件列表实时摄像机MP3、电影和 PDF…...

Spring AOP

Spring AOP 文章目录Spring AOP1.概念1.面向切面编程2.AOP的目的3.AOP实现的分类4.AOP 术语2. Spring AOP的特性1.能力与目标2.AOP机制1.理解SpringAOP的代理2.AOP代理类的自调用代码的粒度如何让自调用走代理&#xff1f;3.Enabling AspectJ Support3. 定义切面与切点1. 声明切…...

【消费战略方法论】认识消费者的恒常原理(一):消费者稳态平衡原理

“消费战略”是塔望咨询基于大量的战略与营销实践经验结合心理学、经济学、传播学等相关专业学科的知识应用进行提炼与创造形成的战略方法体系。消费战略强调以消费者为导向&#xff0c;进行企业、品牌战略、品牌营销的制订和落地&#xff0c;企业经营的每个环节和输出的每个动…...

python居然能语音控制电脑壁纸切换,只需60行代码

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! 家在日常的电脑使用中&#xff0c;都会有自己喜爱类型的桌面 单纯的桌面有时候会让人觉得单调 今天&#xff0c;就由我带领大家只用60行代码打造一款语音壁纸切换器程序&#xff0c; 让大家能够通过语音的方式来控制电脑去…...

内存泄露定位手段(c语言hook malloc相关方式)

如何确定有内存泄露问题&#xff0c;如何定位到内存泄露位置&#xff0c;如何写一个内存泄漏检测工具&#xff1f; 1&#xff1a;概述 内存泄露本质&#xff1a;其实就是申请调用malloc/new&#xff0c;但是释放调用free/delete有遗漏&#xff0c;或者重复释放的问题。 内存…...

STM32 CAN波特率计算

STM32 CAN波特率计算简介CAN总线收发&#xff0c;中断方式接收配置代码部分reference简介 CAN通信帧共分为数据帧、远程帧、错误帧、过载帧和帧间隔&#xff0c;本文这里以数据帧为例。 显性电平对应逻辑0&#xff0c;CAN_H和CAN_L之差为2.5V左右。而隐性电平对应逻辑1&#x…...

C/C++ 中#define 的妙用,让代码更美一些

C/C 中#define 的妙用&#xff0c;让代码更美一些 flyfish 1 数值类型输出易读的字符串形式 例如使用enum定义一些错误值&#xff0c;想要将数值类型的错误&#xff0c;输出易读的字符串形式 重要的一句代码 #define MAKE_PAIR(val) std::make_pair(val, #val)可以看到 #va…...

Linux文件系统操作与磁盘管理

查看磁盘和目录的容量 使用 df 命令查看磁盘的容量 df在实验楼的环境中你将看到如下的输出内容&#xff1a; 但在实际的物理主机上会更像这样&#xff1a; 物理主机上的 /dev/sda2 是对应着主机硬盘的分区&#xff0c;后面的数字表示分区号&#xff0c;数字前面的字母 a 表示…...

【Python】批量采集原神表情包~

嗨害大家好鸭~我是小熊猫(✿◡‿◡) 最近迷上了原神&#xff0c; 不自觉中就很喜欢保存广大旅行者制作的表情包~ 真的很有意思诶~ 源码资料电子书:点击此处跳转文末名片获取 一个个保存的话&#xff0c;好像效率很低嘛… 那我就发挥我小熊猫的老本行直接给把他们全部采集下…...

C语言基本语法注释类型关键字

C 基本语法 标识符 给变量所取的名字叫变量名&#xff0c;定义变量的名字需要遵循标识符的命名规则。 标识符是用来标识变量、符号常量、数组、函数、文件等名字的有效字符序列。 标识符的命名规则&#xff1a; 1.只能由字母、数字和下划线组成&#xff08;例如&#xff1a…...

【C ++】C++入门知识(二)

C入门&#xff08;二&#xff09; 作者&#xff1a;小卢 专栏&#xff1a;《C》 喜欢的话&#xff1a;世间因为少年的挺身而出&#xff0c;而更加瑰丽。 ——《人民日报》 1.引用 1.1.引用的概念及应用 引用&#xff08;&&#xff09; 引用不是新定义一个变量&#xff0…...

qt qchart学习

Qt Charts主要由QChartView、QChart、QLegend图例、坐标轴(由QAbstractAxis子类实现)、**数据源(由QAbstractSeries子类实现)**等组成使用QChart的前期准备1. Qt5.9及以上版本&#xff1b;2. .pro文件中添加QT charts3. 在使用QChart的各个控件之前&#xff0c;引用头文件并必…...

手工布署 java 项目

新建一个java springboot项目 maven 这是一个非常简易的 springBoot 的项目 使用 maven 的 package 工具进行打包 把包上传到 linux 的机器上&#xff0c; 确保 linux 机器上安装了 java jdk工具&#xff0c; 并且配置好了 JAVA_HOME 注意&#xff0c;helloworld 默认的是要使…...

《设计模式》观察者模式

《设计模式》观察者模式 观察者模式是一种行为型设计模式&#xff0c;它定义了一种一对多的依赖关系&#xff0c;让多个观察者对象可以同时监听和相应被观察者对象的状态变化&#xff0c;以达到解耦和复用的目的。观察者模式的优点如下&#xff1a; 解耦&#xff1a;观察者模…...

基于SpringBoot的外卖项目(详细开发过程)

基于SpringBootMyBatisPlus的外卖项目1、软件开发整体介绍软件开发流程角色分工2、外卖项目介绍项目介绍产品展示后台系统管理移动端技术选型功能结构角色3、开发环境的搭建开发环境说明建库建表Maven项目搭建项目的目录结构pom.xmlapplication.ymlReggieApplication启动类配置…...

ChatGPT 研发传言席卷互联网公司,这会是一门好生意吗?

ChatGPT&#xff08;也称GPT-3&#xff09;是一种基于人工智能的自然语言生成模型&#xff0c;由OpenAI团队开发。它是GPT系列模型的最新版本&#xff0c;于2020年6月发布。ChatGPT的由来GPT-1是在2018年发布的第一个版本&#xff0c;使用了12亿个参数。随后&#xff0c;GPT-2在…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...