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

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...