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

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...

Heygem50系显卡合成的视频声音杂音模糊解决方案

如果你在使用50系显卡有杂音的情况&#xff0c;可能还是官方适配问题&#xff0c;可以使用以下方案进行解决&#xff1a; 方案一&#xff1a;剪映替换音色&#xff08;简单适合普通玩家&#xff09; 使用剪映换音色即可&#xff0c;口型还是对上的&#xff0c;没有剪映vip的&…...

河北对口计算机高考MySQL笔记(完结版)(2026高考)持续更新~~~~

MySQL 基础概念 数据&#xff08;Data&#xff09;&#xff1a;文本&#xff0c;数字&#xff0c;图片&#xff0c;视频&#xff0c;音频等多种表现形式&#xff0c;能够被计算机存储和处理。 **数据库&#xff08;Data Base—简称DB&#xff09;&#xff1a;**存储数据的仓库…...