题目描述
435. Non-overlapping Intervals
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Note:
- You may assume the interval’s end point is always bigger than its start point.
- Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.
题意:给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
题解:绝大部分涉及到区间的题目第一步要做的都是按照左端点或者右端点进行排序,排好序后找到其中的递推关系。具体到这一题,我们可以先把问题转化成最多能找到多少个互不重叠的区间。基于此,我们可以有如下的几种贪心思路:
算法1
(按照区间终点排序) $O(nlogn)$
题解1:按照右端点进行排序。如果当前区间的左端点大于等于前一个区间的右端点,说明当前区间可以是一个独立的区间,我们可以保存它,如果当前区间的左端点小于前一个区间的右端点,说明当前区间和前面一个区间重合了,我们需要删除一个区间,那么删除哪个更好呢?很明显是当前这个,因为下一个区间如果和前面那个区间重合了,也肯定和当前区间重合,这时候又要删除一个区间,但是下一个区间如果和当前区间重合,那么把当前区间删除后,不一定会和前面的区间重合。所以不论是Case 2
还是Case 3
我们都应该删除current
区间。因此我们只需要不断的维护前一个保留区间的右端点即可,只有当当前区间的左端点大于前一个保留区间右端点时,我们才更新保留区间。
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() < 2) return 0;
sort(intervals.begin(),intervals.end(),[](const vector<int>&a,const vector<int>&b)
{
return a[1] == b[1] ? a[0] > b[0]:a[1] < b[1];
});
int n = intervals.size(),cnt = 1,cur_right = intervals[0][1];
for(int i = 1 ; i < n ; i ++)
{
if(intervals[i][0] >= cur_right)
{
cnt ++;
cur_right = intervals[i][1];
}
}
return n - cnt;
}
算法2
(按照左端点排序) $O(nlogn)$
题解2:当然了,我们也可以按照左端点对区间进行排序,我们也保存最后一个保留区间的右端点的值。那么有如下三种情况:
Case 1
:这时候说明不发生重叠,那么我们可以同时保留这两个区间,更新最后一个保留区间
Case 2
:这时候我们倾向于删除上一个保留区间,而把当前区间保存下来。
Case 3
:这时候我们则倾向于删除当前区间。这是因为,考虑再来一个区间C
,如果它的左端点小于B
的左端点,那么A,B,C
最多只能保留一个,如果它的左端点大于B
的左端点,那么我们可以同时保留A,C
,而不是B,C
,如果它的左端点大于B
的右端点,那么可以同时保留A,C
或B,C
。综上,保留A
是更优的解法。
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() < 2) return 0;
sort(intervals.begin(),intervals.end(),[](const vector<int>&a,const vector<int>&b)
{
return a[0] < b[0];
});
int n = intervals.size(),cnt = 1,cur_right = intervals[0][1];
for(int i = 1 ; i < n ; i ++)
{
if(intervals[i][0] >= cur_right)
{
cnt ++;
cur_right = intervals[i][1];
}else if(intervals[i][1] < cur_right)
cur_right = intervals[i][1];
}
return n - cnt;
}
(按照左端点排序) 的第三种情况保留 靠左边的区间应该是 cur_right = min(intervals[i][1], cur_right); 但是leetcode 提交都能通过