-
无重叠区间
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [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后,来一个4-6,又来一个3-5,无疑会对计算造成负担,因为我们貌似只能用i*j的数量级去每个区间往后遍历看i区间的区间尾部是否会比j的区间头部大,大的话就重叠。
考虑到上述会比较麻烦,虽然也可以解出,但我们可以通过先对每个区间尾部大小进行排序,区间按尾部大小排好序后,从左往右遍历时不断判定是否重叠即可。
代码如下(含代码注释):
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(), [](vector<int>a1,vector<int>a2){return a1[1]<a2[1];
});//按照区间尾部大小的关键字进行排序
int count=0,i,pre;
pre=intervals[0][1];
for(i=1;i<intervals.size();i++)
{
if(intervals[i][0]<pre)//如果后面的区间开头比前面记录的区间尾部pre要小,说明区间重叠
count++;
else
{
pre=intervals[i][1];//区间没重叠,pre变为更大的区间的尾部
}
}
return count;
}
};
觉得该篇文章有用的请不要忘记忘记点击右下角的大拇指~
欢迎大家关注我的公众号:Smooth前端成长记录
公众号同步更新CSDN博客内容,想方便阅读博客的C友可以来关注我的公众号以便获得更优良的阅读体验~
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIyVGduV2YfNWawNyZwpmL4cDOyYzN4kjM5ETNyU2M5YGOhRjNlJGOhljZyMDOyI2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)