力扣leetcode 435. 无重叠区间 - 贪心
2024-09-24 15:25:47
非常经典的区间贪心思想 -- 详见博文: 贪心思想之区间贪心
本题给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [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
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
题解
class Solution {
public:
static bool cmp(vector<int>a,vector<int>b){
return a[1]<b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
//按照区间终结点,从小到大排序
sort(intervals.begin(), intervals.end(),cmp);
//获取最小的,区间终结点
int end = intervals[0][1];
int res = 0;
for (int i = 1; i < intervals.size(); ++i) {
//如果区间的起点,小于上一个区间的终点,说明有交集,要删除
if (intervals[i][0] < end) {
++res;
} else {
//没有交集,更新end
end = intervals[i][1];
}
}
return res;
}
};
最新文章
- nodejs复习01
- jQuery对表单的操作
- dbca静默建库和删除库
- Network-POJ3694并查集+LCA
- java中的包以及内部类的介绍
- js获得控件位置
- Python 文件操作模块 shutil 详解
- 基于开源 Openfire 聊天服务器 - 开发Openfire聊天记录插件[转]
- TRS_WCM(拓尔思信息技术有限公司)内容协作平台平台置标经验攻略
- kloxo面板教程-折腾了一天
- 【bzoj1552】[Cerc2007]robotic sort
- 一句话了解JAVA与大数据之间的关系
- linux使用windows磁盘,挂载共享目录
- join和+的区别
- Long类型参数传到前端精度丢失的解决方案
- 解决scrapy报错:ModuleNotFoundError: No module named &#39;win32api&#39;
- Spring Cloud Netflix Eureka: 多网卡环境下Eureka服务注册IP选择问题
- C_求两个日期相隔的天数(闰年)
- I/O系统(一)
- python系统编码转换
热门文章
- PHP xml_parser_create() 函数
- C/C++编程笔记:C语言NULL值和数字 0 值区别及NULL详解
- 新手程序员求职简历缺少这 3 点!别说8k薪资,4K你可能都拿不到!
- luogu P6583 回首过去 简单数论变换 简单容斥
- 3.深入k8s:Deployment控制器
- Windows环境编译Spark源码
- day3. 六大标准数据类型的类型转换
- node.js 使用----相关常用命令总结
- (恐怕是)写得最通俗易懂的一篇关于HashMap的文章——xx大佬这样说
- DB2 分组查询语句ROW_NUMBER() OVER() (转载)