😄435.无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [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
• 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

思路

基本思想

与 452题 思路类似，452题是需要找到所有的重叠区间，这里是需要去除所有的重叠区间，让所有的区间都没有重复，所以判断条件与452题类似，先排序，这样才能在遍历容器的时候方便的知道前后两个区间是否重叠

不排序的话就需要依次从每个区间出发，判断他与其他的区间是否重叠从而删除

执行流程

1. 对容器排序，初始flag为第一个区间

2. 遍历容器，没有遇到交集flag就更新为当前区间，遇到交集就删除，在程序中不删除只计数

3. 遇到有交集的两个区间，尽可能保留范围小（靠右）的区间，这样尽可能地保证区间之间的间隔增大

   拿[10,16],[12,14],[15,18]举例，[10,16],[12,14]有交集，留下[12,14]之后就不会与[15,18]有交集，只需要删除一次

   若留下[10,16]，那么与[15,18]还有交集，需要删除两次，所以尽可能留下范围小（贪心）的区间

4. 没遇到交集就将当前flag更新为当前区间

两种更新，有交集更新为范围小的区间，没交集更新为当前区间

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),
        [](vector<int>& v1,vector<int>& v2)->bool{
            //第一元素相等按第二元素升序排列
            if(v1[0]==v2[0])
                return v1[1]<v2[1];
            return v1[0]<v2[0];
        });
        vector<int> flag=intervals[0];
        int res=0;
        for(int i=1;i<intervals.size();++i){
            //与flag作比较,有交集
            if(intervals[i][0]<flag[1]){
                ++res;
                flag=intervals[i][1]<flag[1]?intervals[i]:flag;
            }
            //没有交集
            else{
                flag=intervals[i];
            }
        }
        //返回结果
        return res;
    }
};

总结

与452题一样的思路，一个时统计有多少交集，本题是去除所有交集，由于需要尽可能少的去除交集，所以在两个区间有交集时尽可能的保留范围靠右的小区间（贪心），这样与下一个区间相比时就尽可能的拉开他们之间的举例

当两个区间没有交集时，直接更新flag，判断当前区间与下一个区间是否有交集