无重叠区间-力扣435-java贪心策略
一、题目描述
给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/non-overlapping-intervals
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、运行结果

三、解题思路
这里用的是贪心策略,刚好学习完贪心思想,树上有一道非常类似的题:活动选择。
大致思想就是:先将每个区间按结束时间(第二列)从小到大排列,首先选择第一个区间,然后将与其重叠的区间都移除掉,统计在该区间结束后开始的第一个区间(第一个不和前面的区间重叠的区间),重复进行选择,就可以得到最大不相交子集,总区间的个数减去最大不想交子集中区间的个数就是题目所求的个数。
四、AC代码
class Solution {public int eraseOverlapIntervals(int[][] intervals) {//取出最大不相交子集中区间的个数,总区间个数减去该数就是所求int n = intervals.length;Arrays.sort(intervals, new Comparator<int[]>(){ //按第二列(结束时间)对数组排序public int compare(int[] o1, int[] o2){if(o1[1] == o2[1])return o1[0]-o2[0];return o1[1] - o2[1];}});int count = 1, endTime = intervals[0][1]; for(int i=1; i<n; i++){if(intervals[i][0] >= endTime) { //开始时间在前面的结束时间之后endTime = intervals[i][1];count++;}}return n-count;}
}
相关文章:
无重叠区间-力扣435-java贪心策略
一、题目描述给定一个区间的集合 intervals ,其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。示例 1:输入: intervals [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后,剩下的区间没有重叠。…...
Python使用VTK对容积超声图像进行体绘制(三维重建)
目录VTK简介什么是体绘制?体绘制效果图流程CodeQ&AReferenceVTK简介 VTK(Visualization Toolkit)是一个用于3D计算机图形学、图像处理和可视化的开源软件包。它包括一组C类和工具,可以让用户创建和处理复杂的3D图形和数据可视…...
JAVA设计模式之工厂模式讲解
目录 前言 开始表演 前言 Java中使用工厂模式的主要原因是为了实现代码的灵活性和可维护性。工厂模式是一种创建型设计模式,它提供了一种将对象的创建和使用进行分离的方式。具体来说,工厂模式可以将对象的创建过程封装在一个独立的工厂类中ÿ…...
近万字概述L3及以上自动驾驶故障运行和故障安全机制
本文描述了对ADS的FO和FS机制的评估方法。当系统不能按预期运行时,ADS将使用FO和FS机制。这些机制使ADS能够在最大程度上达到使车辆及其乘员脱离危险的MRC。定义、测试和验证实现MRC的FO和FS策略是确保ADS安全运行和部署的重要步骤。 MRC在SAE J3016中被定义为: 用户或ADS在…...
kafka入门到精通
文章目录一、kafka概述?1.定义1.2消息队列1.2.1 传统消息队列的使用场景1.2.2 消息队列好处1.2.3 消息队列两种模式1.3 kafka基础架构二、kafka快速入门1.1使用docker-compose安装kafka1.2测试访问kafka-manager1.3 查看kafka版本号1.4 查看zookeeper版本号1.5 扩展…...
es-09模糊查询
模糊查询 前缀搜索:prefix 概念:以xx开头的搜索,不计算相关度评分。 注意: 前缀搜索匹配的是term,而不是field。前缀搜索的性能很差前缀搜索没有缓存前缀搜索尽可能把前缀长度设置的更长 语法: GET <ind…...
57 - 深入解析任务调度
---- 整理自狄泰软件唐佐林老师课程 文章目录1. 问题1.1 思考1.2 实例分析:问题分析及解决2. 深入讨论2.1 任务调度的定义2.2 关于调度算法的分类2.3 什么时候进行任务调度2.4 任务的分类2.5 关于优先级调度2.6 问题2.7 调度算法的终极目标2.8 课后扩展1. 问题 系统…...
CAN总线开发一本全(3) - 微控制器集成的FlexCAN外设
CAN总线开发一本全(3) - 微控制器集成的FlexCAN外设 苏勇,2023年2月 文章目录CAN总线开发一本全(3) - 微控制器集成的FlexCAN外设引言硬件外设模块系统概要总线接口单元 - 寄存器清单数据结构 - 消息缓冲区MB初始化过…...
Elasticsearch7.8.0版本进阶——段合并
目录一、段的概述1.1、段的概念1.2、段的缺点1.3、如何解决段数量暴增问题二、段合并的流程三、段合并的注意事项一、段的概述 1.1、段的概念 每一 段 本身都是一个倒排索引。 1.2、段的缺点 由于自动刷新流程每秒会创建一个新的段 ,这样会导致短时间内的段数量…...
Java版贪食蛇游戏
技术:Java等摘要:近年来Java作为一种新的编程语言,以其简单性、可移植性和平台无关性等优点,得到了广泛地应用,特别是Java与万维网的完美结合,使其成为网络编程和嵌入式编程领域的首选编程语言。MyEclipse是…...
2023年度数学建模竞赛汇总
本人7年数学建模竞赛经验,历史获奖率百分之百。团队成员都是拿过全国一等奖的硕博,有需要数模竞赛帮助的可以私信我。 下面主要列几年一些比较有含金量的数学建模竞赛(按比赛时间顺序) 1. 美国大学生数学建模竞赛 报名时间&…...
了解Python语言和版本
1.1 任务1了解Python语言和版本 Python 语言的名字来自于一个著名的电视剧"Monty Pythons Flying Cireus",Python之父 Guido van Rossum是这部电视剧的狂热爱好者,所以把他设计的语言命名为Python。 Python 是一门跨平台、开源、免费的解释型高级动态编…...
nvm (node版本管理工具)安装的详细步骤,并解决安装过程中遇到的问题
1、下载NVM,跳转下载链接后,如下图,下载红框后解压文件 2、安装 注意:双击安装之后,会有两个地址选择, 1、地址中不能存在空格 2、不要放在C盘中,后面需要改个设置文件,安装到C盘的…...
朴素贝叶斯笔记
贝叶斯公式在A 条件成立下,B的概率等于B的概率*在B条件成立下,A的概率/A的概率,推导假设一个学校中男生占总数的60%,女生占总数的40%。并且男生总是穿长裤,女生则一半穿长裤、一半穿裙子。1.正向概率。随机选取一个学生…...
【GUI】用于电动助力车性能分析的GUI(Matlab代码实现)
👨🎓个人主页:研学社的博客💥💥💞💞欢迎来到本博客❤️❤️💥💥🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密…...
Android:反编译apk踩坑/apktool/dex2jar/JDGUI
需求描述 想要反编译apk文件,搜到了这篇博客:Android APK反编译就这么简单 详解(附图),非常有参考价值~但其中的工具下载链接都已404,而本杂鱼实际操作的过程中也出现了亿点点点点点点的问题,于…...
React 跨域的配置
1、为什么会出现跨域? 浏览器遵循同源政策(同源策略三要素:协议相同、域名相同、端口相同) 2、配置跨域代理 使用中间件 http-proxy-middleware(安装依赖) npm install http-proxy-middleware 创建setupP…...
Elasticsearch7.8.0版本进阶——持久化变更
目录一、持久化变更的概述二、事务日志(translog)三、持久化变更完整流程四、事务日志(translog)的作用五、事务日志(translog)的目的一、持久化变更的概述 没有用 fsync 把数据从文件系统缓存刷ÿ…...
CF Edu 127 A-E vp补题
CF Edu 127 A-D vp补题 继续每日一vp,今天晚上有课,时间不太多,回去就直接vp。前三题比较简单,过了之后排名rk2000,然后就去洗澡了。d题没怎么认真思考,其实也可做。最后rk4000。发挥还行,b题罚…...
剑指 Offer 05. 替换空格
摘要 剑指 Offer 05. 替换空格 一、字符替换 由于每次替换从1个字符变成3个字符,使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的3倍,这样可保证字符数组可以容纳所有替换后的字符。 获得 s 的长度 length创建字符数组 array&#x…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
