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

【LeetCode-435】无重叠区间(贪心)

题目链接

题目简介

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

示例 1:

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

示例 2:

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

示例 3:

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

解法:贪心

相信刚开始看到这道题目都冥冥之中感觉要排序和我前几天做的很类似,都是需要提前固定好一个变量

我来按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了

此时问题就是要求非交叉区间的最大个数。

区间,1,2,3,4,5,6都按照右边界排好序。

当确定区间 1 和 区间2 重叠后,如何确定是否与 区间3 也重贴呢?

就是取 区间1 和 区间2 右边界的最小值,因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分,如果这个最小值也触达到区间3,那么说明 区间 1,2,3都是重合的。

接下来就是找大于区间1结束位置的区间,是从区间4开始。那有同学问了为什么不从区间5开始?别忘了已经是按照右边界排序的了

区间4结束之后,再找到区间6,所以一共记录非交叉区间的个数是三个。

总共区间个数为6,减去非交叉区间的个数3。移除区间的最小数量就是3。

代码实现


class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)-> {return Integer.compare(a[0],b[0]);});int count = 1;for(int i = 1;i < intervals.length;i++){if(intervals[i][0] < intervals[i-1][1]){intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);continue;}else{count++;}    }return intervals.length - count;}
}

相关文章:

【LeetCode-435】无重叠区间(贪心)

题目链接 题目简介 给定一个区间的集合&#xff0c;找到需要移除区间的最小数量&#xff0c;使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”&#xff0c;但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4…...

写读后感的时候,可以适当地引用书中的内容吗?

写读后感时&#xff0c;适当地引用书中的内容是可以的&#xff0c;这样可以更好地支持你的观点和感受&#xff0c;增强文章的可信度和说服力。 引用书中的内容可以帮助读者更好地理解你所讨论的主题和人物&#xff0c;同时也可以展示你对原著的深入理解和阅读能力。但是&#…...

RockChip DRM Display Driver

资料来源: 《Rockchip_DRM_Display_Driver_Development_Guide_V1.0.pdf》 《Rockchip_Developer_Guide_DRM_Display_Driver_CN.pdf》 一:DRM概述 DRM(Direct Rendering Manager)直接渲染管理,buffer分配,帧缓冲。对应userspace库位libdrm,libdrm库提供了一系列友好的…...

【数据库】GaussDB数据类型和简单DDL概述

GaussDB是一款华为公司开发的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;提供了多种数据类型用于存储和处理不同类型的数据。以下是GaussDB常见的数据类型&#xff1a; 1、GaussDB常见的数据类型 1.1、数值型&#xff08;Numeric Types&#xff09;&…...

malloc/free和new/delete相关问题:

面试题&#xff1a; 1、两种方式的区别&#xff1a; &#xff08;1&#xff09;malloc需要强制类型转换&#xff0c;new不需要 &#xff08;2&#xff09;malloc需要计算空间大小&#xff0c;new不需要 例如&#xff1a;创建5个int类型的空间 int*p(int *)malloc(sizeof(i…...

设计一套扑克牌

约束和假设 这是一幅用于类似扑克和二十一点等游戏的通用扑克牌吗&#xff1f; 我们可以假设这副牌有52张&#xff08;2-10&#xff0c;杰克&#xff0c;女王&#xff0c;国王&#xff0c;埃斯&#xff09;和4种花色吗&#xff1f; 我们可以假设输入是有效的&#xff0c;还是需…...

ubuntu20.04 外接hdmi没有声音

pulseaudio -k 请尝试执行该命令...

Mybatis 拦截器注册方式

在MyBatis中注册拦截器可以通过以下三种方式&#xff1a; 1. XML配置文件方式 在Mybatis的核心配置文件&#xff08;mybatis-config.xml&#xff09;中的标签下定义拦截器&#xff0c;并指定实现类。 <configuration><!-- ...其他配置... --><plugins><…...

[嵌入式软件][启蒙篇][仿真平台] STM32F103实现SPI控制OLED屏幕

上一篇&#xff1a; [嵌入式软件][启蒙篇][仿真平台] STM32F103实现LED、按键 [嵌入式软件][启蒙篇][仿真平台] STM32F103实现串口输出输入、ADC采集 [嵌入式软件][启蒙篇][仿真平台]STM32F103实现定时器 [嵌入式软件][启蒙篇][仿真平台] STM32F103实现IIC控制OLED屏幕 文章目…...

个体诊所电子处方系统设计,社区门诊处方开单管理系统软件教程

个体诊所电子处方系统设计&#xff0c;社区门诊处方开单管理系统软件教程 一、前言 以下软件程序操作教程以 佳易王诊所电子处方管理系统软件V17.3为例说明 如图&#xff0c;在基本信息设置里&#xff0c;可以设置处方配方模板&#xff0c;这样在开电子处方的时候可以一键导入…...

数据结构(1)--> 顺序表

定义&#xff1a; 顺序表存储定义&#xff1a; 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构&#xff0c;顺序表功能的实现借助于数组&#xff0c;通过对数组进行封装&#xff0c;从而实现增删查改的功能&#xff0c;严格意义上来说&#xff08;数组无法实现…...

排序算法经典模型: 梯度提升决策树(GBDT)的应用实战

目录 一、Boosting训练与预测 二、梯度增强的思想核心 三、如何构造弱学习器和加权平均的权重 四、损失函数 五、梯度增强决策树 六、GBDT生成新特征 主要思想 构造流程 七、梯度增强决策树以及在搜索的应用 7.1 GDBT模型调参 7.1.1 框架层面参数 n_estimators su…...

【揭秘】ForkJoinTask全面解析

内容摘要 ForkJoinTask的显著优点在于其高效的并行处理能力&#xff0c;它能够将复杂任务拆分成多个子任务&#xff0c;并利用多核处理器同时执行&#xff0c;从而显著提升计算性能&#xff0c;此外&#xff0c;ForkJoinTask还提供了简洁的API和强大的任务管理机制&#xff0c…...

如何利用数据压缩提高高性能存储的效率?

在当前信息爆炸的时代&#xff0c;大数据存储和管理成为了各大企业和组织面临的重要挑战之一。高性能存储系统的效率对于数据处理和应用的性能至关重要。而数据压缩技术的应用可以在一定程度上提高高性能存储的效率。 数据压缩技术的作用 数据压缩是通过对数据进行编码和压缩…...

前端工程化之:webpack1-2(安装与使用)

一、webpack简介 webpack中文网 webpack 是基于模块化的打包(构建)工具&#xff0c;它把一切视为模块它通过一个开发时态的入口模块为起点&#xff0c;分析出所有的依赖关系&#xff0c;然后经过一系列的过程(压缩、合并)&#xff0c;最终生成运行时态的文件。 webpack的特点&a…...

MySQL索引类型及数据结构【笔记】

1 索引类型 返回面试宝典 主键索引&#xff08;PRIMARY&#xff09;:数据列不允许重复&#xff0c;不允许为NULL&#xff0c;一个表只能有一个主键。 唯一索引&#xff08;UNIQUE&#xff09;:数据列不允许重复&#xff0c;允许为NULL&#xff0c;一个表允许多个列创建唯一索引…...

成熟的内外网数据交换方案,如何实现跨网传输?

网络迅速发展&#xff0c;我们可以从网络上查找到各式各样的信息&#xff0c;但是同时网络安全问题也随之严重。近几年&#xff0c;各种有关网络安全的新闻不断被报道&#xff0c;数据泄露给很多企业带来了严重打击&#xff0c;不仅是经济损失&#xff0c;严重者还会对企业的声…...

python11-Python的字符串之repr

有时候&#xff0c;我们需要将字符串与数值进行拼接&#xff0c;而 Python 不允许直接拼接数值和字符串&#xff0c;程序必须先将数值转换成字符串。 为了将数值转换成字符串&#xff0c;可以使用str0或repr()函数&#xff0c;例如如下代码。 # !/usr/bin/env python# -*- co…...

python小项目:口令保管箱

代码&#xff1a; #! python3 # python 编程-----口令保管箱passwords{emails: F7minlBDDuvMJuxESSKHFhTxFtjVB6,blog:VmALvQyKAxiVH5G8v01if1MLZF3sdt,luggage:12345,} import sys,pyperclip if len(sys.argv)<2:print(usage:python python3文件[accout]-copy accout pass…...

微认证 openEuler社区开源贡献实践

文章目录 1. 开源与开源社区2. openEuler 社区概述3.参与openEuler社区贡献4.openEuler软件包开发Linux软件管理——源码编译 1. 开源与开源社区 Richard Matthew Stallman&#xff0c;1983年9月推出GNU项目&#xff0c;并发起自由软件运动(free software movement或free/open…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...