当前位置: 首页 > 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在…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...