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

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...