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

Java——无重叠区间

题目链接

leetcode在线oj题——无重叠区间

题目描述

给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。

题目示例

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

题目提示

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

解题思路

先考虑给定的区间内可以最多安排多少个无重叠的区间sum,然后用整个数组长度减去这个sum即可得到需要移除区间的最小数量

如果按照起始点和结束点之间的距离排序,从小到大,使用贪心算法尽可能的安排所有距离最短的区间

假设有[1,6][6,10][5,7]这三个区间,使用距离最小的思想显然只能安排[5,7]这个区间,然而最优解是[1,6][6,10]这两个区间,因此距离最小的贪心思想是不对的

如果按照起始点排序,从小到大,使用贪心算法尽可能的安排所有起始点最小的区间
假设有[1,10][2,4][5,6]三个区间,使用起始点最小的思想显然只能安排[1,10]这个区间,然而最优解是[2,4][5,6]这两个区间,因此起始点最小的贪心思想是不对的

如果按照结束点排序,从小到大,使用贪心算法尽可能的安排所有结束点最小的区间
可以发现这种思想得到的结果是正确的

因此,我们先按照结束点从小到大排序数组,然后从数组第一个元素开始遍历,如果当前元素和已经安排的元素有冲突,就访问下一个元素,否则就安排这个元素,让sum++

最后让intervals.length - sum即可得到答案

代码

class Solution {public class compare implements Comparator<int[]>{@Overridepublic int compare(int[] arr1, int[] arr2){return arr1[1] - arr2[1];}}public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, new compare());int sum = 1;int index = 0;for (int i = 1; i < intervals.length; i++) {if(intervals[i][0] >= intervals[index][1]){sum++;index = i;}}return intervals.length - sum;}
}

相关文章:

Java——无重叠区间

题目链接 leetcode在线oj题——无重叠区间 题目描述 给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。 题目示例 输入: intervals [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释…...

数据库和数据表创建与管理操作

数据库和数据表创建与管理操作 MySQL中&#xff0c;一个完整的而数据存储过程主要分成4步&#xff1a; 创建数据库确认字段创建数据表插入数据 标识符命名规则 数据库名、表名不得超过30个字符&#xff0c;变量名限制为29个必须只能包含 A–Z, a–z, 0–9, _共63个字符数据…...

buu [ACTF新生赛2020]crypto-rsa3 1

题目描述&#xff1a; from flag import FLAG from Cryptodome.Util.number import * import gmpy2 import random e65537 p getPrime(512) q int(gmpy2.next_prime) n p*q m bytes_to_long(FLAG) c pow(m,e,n) print(n) print( c ) n 177606504836499246970959030226871…...

知识库:在医疗行业的知识管理有着怎样的意义与实际影响?

知识库中还可存在一个通常被称作典型方法库的特殊部分。如果对于某些问题的解决途径是肯定和必然的&#xff0c;就可以把其作为一部分相当肯定的问题解决途径直接存储在典型方法库中。这种宏观的存储将构成知识库的另一部分。在使用这部分时&#xff0c;机器推理将只限于选用典…...

带你一步步搭建Web自动化测试框架

测试框架的设计有两种思路&#xff0c;一种是自底向上&#xff0c;从脚本逐步演变完善成框架&#xff0c;这种适合新手了解框架的演变过程。另一种则是自顶向下&#xff0c;直接设计框架结构和选取各种问题的解决方案&#xff0c;这种适合有较多框架事件经验的人。本章和下一张…...

Redis进阶-缓存问题

Redis 最常用的一个场景就是作为缓存&#xff0c;本文主要探讨Redis作为缓存&#xff0c;在实践中可能会有哪些问题&#xff1f;比如一致性、击穿、穿透、雪崩、污染等。 为什么要理解Redis缓存问题 在高并发业务场景下&#xff0c;数据库大多数情况都是用户并发访问最薄弱的…...

VS Code Spring 全新功能来了!

大家好&#xff0c;欢迎来到我们 2023 年的第一篇博客&#xff01;我们想与您分享几个与 Spring 插件、代码编辑和性能相关的激动人心的更新&#xff0c;让我们开始吧&#xff01; Spring 插件包的新入门演练 演练&#xff08;Walkthrough&#xff09; 是一种多步骤、向导式的体…...

关于大数据导入流程引擎ccflow的方案

问题&#xff1a; 1. 现在的流程系统里有几百万条已经运行的流程其它的流程架构上 2. 需要把这样的数据导入到ccflow流程引擎里面去。 数据结构分析: 1. ccflow有流程引擎注册表&#xff0c;工作人表&#xff0c;业务数据表与日志表4大表. 2. ccflow的流程实例是一个int类型的…...

AI 生成二次元女孩,免费云端部署(仅需5分钟)

首先需要google的colab&#xff0c;免费版本GPU有额度。其次&#xff0c;打开github网站&#xff0c;选择一个进入colab,修改代码 !apt-get -y install -qq aria2 !pip install -q https://github.com/camenduru/stable-diffusion-webui-colab/releases/download/0.0.16/xforme…...

掌握MySQL分库分表(六)解决主键重复问题--Snowflake雪花算法

文章目录问题及需求常用ID解决方案数据库自增IDUUIDRedis发号器Snowflake雪花算法分布式 ID 生成算法Snowflake原理关于bit与byte雪花算法的位数Snowflake必须注意的地方全局唯⼀、不能重复保证各个系统时间一致Snowflake雪花算法实现雪花算法测试结果问题及需求 单库下⼀般使…...

Melis4.0[D1s]:1.启动流程(与adc按键初始化相关部分)跟踪笔记

文章目录1.启动流程1.1 最先进入的文件&#xff1a;head_s.S1.2 start_kernel()函数所在的文件&#xff1a;init.c1.3 input_init()函数所在文件&#xff1a;sys_input.c1.4 INPUT_LKeyDevInit()所在文件&#xff1a;keyboarddev.c1.5 esINPUT_RegLdev()所在文件&#xff1a;in…...

GNU make 中文手册 第三章:Makefile 总述

一、Makefile 总述 3.1 Makefile 的内容 在一个完整的 Makefile 中&#xff0c;包含了 5 个东西&#xff1a;显式规则、隐含规则、变量定义、指示符和注释。关于“规则”、“变量” 和 “Makefile 指示符” 将在后续的章节进行详细的讨论。本章讨论的是一些基本概念。 显式规…...

简历的专业技能怎么写?排版需要注意的事项

一、简历的专业技能怎么写? 首先,先问一下你自己会什么,然后看看你意向的公司需要什么。一般HR可能并不太懂技术,所以他在筛选简历的时候可能就盯着你专业技能的关键词来看。对于公司有要求而你不会的技能,你可以花几 天时间学习一下,然后在简历上可以写上自己了解这个技…...

【Git】为什么需要版本控制?版本控制工具有那些?

目录 一、为什么需要版本控制&#xff1f; 二、版本控制工具有那些&#xff1f; &#x1f49f; 创作不易&#xff0c;不妨点赞&#x1f49a;评论❤️收藏&#x1f499;一下 一、为什么需要版本控制&#xff1f; 首先我们要知道什么是版本控制&#xff1f;对版本控制进行文字…...

SSH远程执行Python3 Error: UnicodeEncodeError: ‘ascii‘ codec

首先确定要执行脚本服务器的语言编码环境&#xff0c;执行 # locale -a C en_US.utf8 POSIX # locale LANGen_US.utf8 LC_CTYPE"en_US.utf8" LC_NUMERIC"en_US.utf8" LC_TIME"en_US.utf8" LC_COLLATE"en_US.utf8" LC_MONETARY"…...

极简TypeScript教程--面向对象

在早期的JavaScript开发中&#xff08;ES5&#xff09;我们需要通过函数和原型链来实现类和继承&#xff0c;从ES6开始&#xff0c;引入了class关键字&#xff0c;可以更加方便的定义和使用类。TypeScript作为JavaScript的超集&#xff0c;也是支持使用class关键字的&#xff0…...

java TCP/UDP、Socket、URL网络编程详解

文章目录网络通信协议通信双方地址端口号IP地址InetAddress类Socket 网路编程Socket类的常用构造器Socket类的常用方法UDP协议什么是UDP协议UDP网络编程DatagramSocket 构造方法DatagramSocket 常用方法DatagramPacket常用方法实现步骤单向数据发收的UDP程序双向数据发收的UDP程…...

【C语言】宏

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a;> c语言学习 &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0c;是…...

【测试面试】自我分析+功能+接口自动化+性能测试面试题(大全),知己知彼百战百胜......

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 分析自己和面试企业…...

ASE4N65SE-ASEMI高压MOS管ASE4N65SE

编辑-Z ASE4N65SE在TO-220F封装里的静态漏极源导通电阻&#xff08;RDS(ON)&#xff09;为2.5Ω&#xff0c;是一款N沟道高压MOS管。ASE4N65SE的最大脉冲正向电流ISM为16A&#xff0c;零栅极电压漏极电流(IDSS)为10uA&#xff0c;其工作时耐温度范围为-55~150摄氏度。ASE4N65S…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

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

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

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...