代码随想录 435. 无重叠区间

news/2024/6/23 18:35:29

题目
给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

解题思路
首先得判断是否存在重叠,对intervals排序,以每个区间的end来排序,然后遍历intervals,用count计数,如果当前区间的起始值小于上个区间的end,则说明有重叠,需要删除当前区间,count自增。否则说明没重叠,更新end为新区间的end,继续遍历intervals。最后返回count.

代码实现

class Solution {
public:static bool compare(vector<int>& a, vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) {return 0;}sort(intervals.begin(), intervals.end(), compare);int count = 0;int end = intervals[0][1];for (int i=1; i<intervals.size(); i++) {if (intervals[i][0] < end) {count++;} else {end = intervals[i][1];}}return count;}
};

https://www.xjx100.cn/news/3118972.html

相关文章

【Openstack Train安装】五、Memcached/Etcd安装

本文介绍Memcached/Etcd安装步骤&#xff0c;Memcached/Etcd仅需在控制节点安装。 在按照本教程安装之前&#xff0c;请确保完成以下配置&#xff1a; 【Openstack Train安装】一、虚拟机创建 【Openstack Train安装】二、NTP安装 【Openstack Train安装】三、openstack安装…

让 OpenAI GPT4 出 10 道题测试其他开源大语言模型

让 OpenAI GPT4 出 10 道题测试其他开源大语言模型 1. 中文题目及答案2. 日文题目及答案3. 英文题目及答案 1. 中文题目及答案 数学题&#xff1a;一个矩形的长是10厘米&#xff0c;宽是5厘米&#xff0c;求它的面积。 答案&#xff1a;面积 长 x 宽 10厘米 x 5厘米 50平方厘…

YOLOv5原创改进:全维动态卷积再改进,GCODConv

目录 一、原理 网络结构 二、代码 三、应用到YOLOv5中 一、原理

VUE本地idea启动

安装yarn&#xff08;也可以用npm&#xff09; 问题&#xff1a;yarn : 无法加载文件 C:\Users\xx/yarn.ps1&#xff0c;因为在此系统上禁止运行脚本 解决办法&#xff1a;管理员身份运行【 PowerShell】&#xff0c;然后执行【Set-ExecutionPolicy RemoteSigned】&#xff0c…

Echarts大屏可视化_02 球体模块制作

继续跟着b站大佬pink老师学大屏可视化 球体模块制作 1.球体模块布局 HTML <div class"column"><div class"no"><div class"no-hd"><ul><li>125811</li><li>104563</li></ul></div&g…

Oracle研学-基础操作

学自B站黑马程序员笔记 一 创建表空间(创建数据文件) 创建表空间同时会创建一个数据文件(下面5行应该是一句话)&#xff0c;表空间在PLSQL的Object的tablespace中可以看到 create tablespace waterboss //创建表空间 datafile c:\waterboss.dbf //创建表空间对应的…

前端纯js导入导出json配置文件

在做后台系统需求的时候&#xff0c;有个需求是需要把当前表单配置导出&#xff0c;在另一个配置项下&#xff0c;导入这些配置&#xff0c;相当于做了一下配置拷贝。通常我们导出下载一个文件&#xff0c;是先向后端发起请求&#xff0c;由后端处理数据后&#xff0c;再返回文…

37 - 数据库参数设置优化,失之毫厘差之千里

MySQL 是一个灵活性比较强的数据库系统&#xff0c;提供了很多可配置参数&#xff0c;便于我们根据应用和服务器硬件来做定制化数据库服务。如果现在让你回想&#xff0c;你可能觉得在开发的过程中很少去调整 MySQL 的配置参数&#xff0c;但我今天想说的是我们很有必要去深入了…