DAY39：贪心算法（八）无重叠区间+划分字母区间+合并区间

435.无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
1
2
3

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
1
2
3

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
1
2
3

提示:

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= starti < endi <= 5 * 10^4

思路

本题和上一题的引爆气球有点像，也是重叠区间的问题。本题是判断删掉多少个区间，能够得到不重合的区间组合。如下图：

第一步仍然是按照左边界排序，让所有区间按照大小顺序排在一起。

判断相邻两个区间不重叠，也就是i区间左边界>=i-1区间的右边界。

if(i>0&&nums[i][0]>nums[i-1][1]){
   
    continue;//不重叠直接继续遍历
}
1
2
3
4

判断区间如果重叠，那么计数+1（重叠的一定要删掉），和气球题目类似，依旧取最小右边界，看看下一个区间是否重叠

else{
   
    result++;
    //修改右边界
    nums[i][1]=min(nums[i][1],nums[i-1][1]);//修改后继续遍历即可
}
1
2
3
4
5
6

完整版

class Solution {
   
public:
    static bool cmp(vector<int>&a,vector<int>&b){
   
        if(a[0]<b[0])  return true;//左边界升序排序
        return false;
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
   
        if(intervals.size()==0) return 0;
        sort(intervals.begin(),intervals.end(),cmp);
        int count=0;
        for(int i=1;i<intervals.size();i++){
   
            if(intervals[i][0]>=intervals[i-1][1])  continue;
            //如果重叠，更新最小右边界
            else{
   
                count++;
                intervals[i][1]=min(intervals[i][1],intervals[i-1][1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20