435. Non-overlapping Intervals (Medium)

傷城~ 2022-11-03 01:43 127阅读 0赞

## 435. Non-overlapping Intervals (Medium) ##

### 题目描述 ###

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。  
输入输出样例  
输入是一个数组，数组由多个长度固定为 2 的数组组成，表示区间的开始和结尾。输出一个  
整数，表示需要移除的区间数量。

Input: [[1,2], [2,4], [1,3]]
    Output: 1

在这个样例中，我们可以移除区间 \[1,3\]，使得剩余的区间 \[\[1,2\], \[2,4\]\] 互不重叠。

### 题解 ###

在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。

具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用 C++ 的Lambda，结合 std::sort() 函数进行自定义排  
序。  
在样例中，排序后的数组为 \[\[1,2\], \[1,3\], \[2,4\]\]。按照我们的贪心策略，首先初始化为区间  
\[1,2\]；由于 \[1,3\] 与 \[1,2\] 相交，我们跳过该区间；由于 \[2,4\] 与 \[1,2\] 不相交，我们将其保留。因  
此最终保留的区间为 \[\[1,2\], \[2,4\]\]。

## 代码 ##

class Solution { 
    public:
        int eraseOverlapIntervals(vector<vector<int>>& intervals) { 
            if(intervals.empty())
                return 0;
            int size=intervals.size();
            // 从小到大排列
            sort(intervals.begin(),intervals.end(),[](vector<int> a,vector<int> b){ 
                return a[1]<b[1];
            });
                    int count=0;
            int prev=intervals[0][1];
            for(int i=1;i<size;i++)
            { 
                // 如果第二个区间的最小边界 小于 总的最大 说明有重合 丢弃 
                if(prev>intervals[i][0])
                { 
                    count++;
                }
                else{ 
                    // 大于就让该边界的最大值等于 总边界的最小
                    prev=intervals[i][1];
                }
            }
            return count;
        }
    };