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

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...

SQL注入篇-sqlmap的配置和使用

在之前的皮卡丘靶场第五期SQL注入的内容中我们谈到了sqlmap&#xff0c;但是由于很多朋友看不了解命令行格式&#xff0c;所以是纯手动获取数据库信息的 接下来我们就用sqlmap来进行皮卡丘靶场的sql注入学习&#xff0c;链接&#xff1a;https://wwhc.lanzoue.com/ifJY32ybh6vc…...