435. 无重叠区间
给定一个区间的集合 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
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104
题解
为了方便比对,首先会排序。接下来考虑,当重叠却不包含时,如[1,5],[3,6]
,应该优先删除哪个呢?
实际上,排序后,下一个元素[start>=3,end]假设为[6,7]
:
- 如果删除
[1,5]
,则[3,6]
和[6,7]
仍然是重叠的,还需要再删除一个; - 如果删除
[3,6]
则[1,5]
和[6,7]
不再重叠,可以消耗更少的删除次数。
当然下一个元素不一定刚好就是与[1,5]
不重叠的,只是说,优先删除[3,6]
,会利于减少后面出现的重叠情况。
另一种情况重叠并且包含,如[1,10],[2,3]
,[2,3]
包含在[1,10]
中,根据之前的理解,为了减少后面出现的重叠情况,应该优先删除较长的元素[1,10]
,这样如果后面出现[4,5]
,将不会与[2,3]
重叠。
那么在编码中,使用变量prev
记录上一个未删除元素的下标,接下来通过当前下标cur
遍历元素:
- 如果出现重叠,
intervals[cur][0]<intervals[prev][1]
,则需要删除一个元素,cnt++
,接下来需要判断是哪种重叠情况:- 当重叠却不包含,如
[1,3] [2,5]
,优先移除[2,5]
,则prev
不变,仍然指向[1,3]
; - 当重叠并且包含,如
[1,5] [2,3]
优先移除[1,5]
,prev
右移动,指向[2,3]
;
- 当重叠却不包含,如
- 不重叠,如
[1,3] [4,5]
,cnt
不需要累计,直接右移动prev
即可;
查看代码
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int cnt=0;
int prev=0;
sort(intervals.begin(),intervals.end());
for(int cur=1;cur<intervals.size();++cur){
//有重叠
if(intervals[cur][0]<intervals[prev][1]){
++cnt;//重叠移除一个
//[1,3] [2,5] 优先移除[2,5],则prev不变,而[1,5] [2,3]优先移除[1,5],prev右移动
if(intervals[cur][1]<=intervals[prev][1]){
prev=cur;
}
}
else{//[1,3] [4,5]不重叠,移动prev即可
prev=cur;
}
}
return cnt;
}
};
标签:prev,重叠,删除,力扣,intervals,移除,区间,435 From: https://www.cnblogs.com/fudanxi/p/17346255.html