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

无重叠区间-力扣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 &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。示例 1:输入: intervals [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后&#xff0c;剩下的区间没有重叠。…...

Python使用VTK对容积超声图像进行体绘制(三维重建)

目录VTK简介什么是体绘制&#xff1f;体绘制效果图流程CodeQ&AReferenceVTK简介 VTK&#xff08;Visualization Toolkit&#xff09;是一个用于3D计算机图形学、图像处理和可视化的开源软件包。它包括一组C类和工具&#xff0c;可以让用户创建和处理复杂的3D图形和数据可视…...

JAVA设计模式之工厂模式讲解

目录 前言 开始表演 前言 Java中使用工厂模式的主要原因是为了实现代码的灵活性和可维护性。工厂模式是一种创建型设计模式&#xff0c;它提供了一种将对象的创建和使用进行分离的方式。具体来说&#xff0c;工厂模式可以将对象的创建过程封装在一个独立的工厂类中&#xff…...

近万字概述L3及以上自动驾驶故障运行和故障安全机制

本文描述了对ADS的FO和FS机制的评估方法。当系统不能按预期运行时,ADS将使用FO和FS机制。这些机制使ADS能够在最大程度上达到使车辆及其乘员脱离危险的MRC。定义、测试和验证实现MRC的FO和FS策略是确保ADS安全运行和部署的重要步骤。 MRC在SAE J3016中被定义为: 用户或ADS在…...

kafka入门到精通

文章目录一、kafka概述&#xff1f;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模糊查询

模糊查询 前缀搜索&#xff1a;prefix 概念&#xff1a;以xx开头的搜索&#xff0c;不计算相关度评分。 注意&#xff1a; 前缀搜索匹配的是term&#xff0c;而不是field。前缀搜索的性能很差前缀搜索没有缓存前缀搜索尽可能把前缀长度设置的更长 语法&#xff1a; GET <ind…...

57 - 深入解析任务调度

---- 整理自狄泰软件唐佐林老师课程 文章目录1. 问题1.1 思考1.2 实例分析&#xff1a;问题分析及解决2. 深入讨论2.1 任务调度的定义2.2 关于调度算法的分类2.3 什么时候进行任务调度2.4 任务的分类2.5 关于优先级调度2.6 问题2.7 调度算法的终极目标2.8 课后扩展1. 问题 系统…...

CAN总线开发一本全(3) - 微控制器集成的FlexCAN外设

CAN总线开发一本全&#xff08;3&#xff09; - 微控制器集成的FlexCAN外设 苏勇&#xff0c;2023年2月 文章目录CAN总线开发一本全&#xff08;3&#xff09; - 微控制器集成的FlexCAN外设引言硬件外设模块系统概要总线接口单元 - 寄存器清单数据结构 - 消息缓冲区MB初始化过…...

Elasticsearch7.8.0版本进阶——段合并

目录一、段的概述1.1、段的概念1.2、段的缺点1.3、如何解决段数量暴增问题二、段合并的流程三、段合并的注意事项一、段的概述 1.1、段的概念 每一 段 本身都是一个倒排索引。 1.2、段的缺点 由于自动刷新流程每秒会创建一个新的段 &#xff0c;这样会导致短时间内的段数量…...

Java版贪食蛇游戏

技术&#xff1a;Java等摘要&#xff1a;近年来Java作为一种新的编程语言&#xff0c;以其简单性、可移植性和平台无关性等优点&#xff0c;得到了广泛地应用&#xff0c;特别是Java与万维网的完美结合&#xff0c;使其成为网络编程和嵌入式编程领域的首选编程语言。MyEclipse是…...

2023年度数学建模竞赛汇总

本人7年数学建模竞赛经验&#xff0c;历史获奖率百分之百。团队成员都是拿过全国一等奖的硕博&#xff0c;有需要数模竞赛帮助的可以私信我。 下面主要列几年一些比较有含金量的数学建模竞赛&#xff08;按比赛时间顺序&#xff09; 1. 美国大学生数学建模竞赛 报名时间&…...

了解Python语言和版本

1.1 任务1了解Python语言和版本 Python 语言的名字来自于一个著名的电视剧"Monty Pythons Flying Cireus",Python之父 Guido van Rossum是这部电视剧的狂热爱好者&#xff0c;所以把他设计的语言命名为Python。 Python 是一门跨平台、开源、免费的解释型高级动态编…...

nvm (node版本管理工具)安装的详细步骤,并解决安装过程中遇到的问题

1、下载NVM&#xff0c;跳转下载链接后&#xff0c;如下图&#xff0c;下载红框后解压文件 2、安装 注意&#xff1a;双击安装之后&#xff0c;会有两个地址选择&#xff0c; 1、地址中不能存在空格 2、不要放在C盘中&#xff0c;后面需要改个设置文件&#xff0c;安装到C盘的…...

朴素贝叶斯笔记

贝叶斯公式在A 条件成立下&#xff0c;B的概率等于B的概率*在B条件成立下&#xff0c;A的概率/A的概率&#xff0c;推导假设一个学校中男生占总数的60%&#xff0c;女生占总数的40%。并且男生总是穿长裤&#xff0c;女生则一半穿长裤、一半穿裙子。1.正向概率。随机选取一个学生…...

【GUI】用于电动助力车性能分析的GUI(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

Android:反编译apk踩坑/apktool/dex2jar/JDGUI

需求描述 想要反编译apk文件&#xff0c;搜到了这篇博客&#xff1a;Android APK反编译就这么简单 详解&#xff08;附图&#xff09;&#xff0c;非常有参考价值~但其中的工具下载链接都已404&#xff0c;而本杂鱼实际操作的过程中也出现了亿点点点点点点的问题&#xff0c;于…...

React 跨域的配置

1、为什么会出现跨域&#xff1f; 浏览器遵循同源政策&#xff08;同源策略三要素&#xff1a;协议相同、域名相同、端口相同&#xff09; 2、配置跨域代理 使用中间件 http-proxy-middleware&#xff08;安装依赖&#xff09; npm install http-proxy-middleware 创建setupP…...

Elasticsearch7.8.0版本进阶——持久化变更

目录一、持久化变更的概述二、事务日志&#xff08;translog&#xff09;三、持久化变更完整流程四、事务日志&#xff08;translog&#xff09;的作用五、事务日志&#xff08;translog&#xff09;的目的一、持久化变更的概述 没有用 fsync 把数据从文件系统缓存刷&#xff…...

CF Edu 127 A-E vp补题

CF Edu 127 A-D vp补题 继续每日一vp&#xff0c;今天晚上有课&#xff0c;时间不太多&#xff0c;回去就直接vp。前三题比较简单&#xff0c;过了之后排名rk2000&#xff0c;然后就去洗澡了。d题没怎么认真思考&#xff0c;其实也可做。最后rk4000。发挥还行&#xff0c;b题罚…...

剑指 Offer 05. 替换空格

摘要 剑指 Offer 05. 替换空格 一、字符替换 由于每次替换从1个字符变成3个字符&#xff0c;使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的3倍&#xff0c;这样可保证字符数组可以容纳所有替换后的字符。 获得 s 的长度 length创建字符数组 array&#x…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...