力扣题解：435. 无重叠区间（中等）

题目

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

示例 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 <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= start_i < end_i <= 5 * 10^4

思路：我们要移除最少的区间使得区间不相互重叠，那么直观来说，我们应该移除区间范围较大的元素，因为其中可能包含很多小区间，使其发生重叠。

那么问题来了，我们怎么知道什么是”范围较大“。显然原始数组十分混乱，不太好判断，这里我们对这些区间以右边界为基准进行排序，使其变成一个比较有序的状态，使用右边界是因为可以使编码更方便。

例如经过排序：

[[1,2],[2,3],[3,4],[1,3]] -> [[1,2],[2,3],[1,3],[5,7]]

我们就可以比较好的定义什么叫”范围较大“。由于升序排序之后，可以很容易判断出最大区间是多少。例如[1,2],[2,3],[5,7]中，可以知道，右边界2->3最大的区间长度是1，右边界3->7最大的区间长度是4，所有区间长度大于最大区间长度的，都定义为”范围较大“，是需要去除的。

进一步观察可以知道，右边界相同的元素，最终最多只能保留一个，因为从右往左看，起点相同，无论他们长度多少，在起点总会重叠。

所以我们最终的想法就变成：对区间进行排序过后，对于所有右边界相同的元素，我们只保留一个区间长度小于最大区间长度的元素。

题解：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    	//以右边界为基准进行升序排序
        sort(intervals.begin(), intervals.end(), [](auto& r, auto& l) {
            return r[1] < l[1];
        });
		
        //记录上一个右边界
        int right = intervals[0][1];
        //满足条件的区间个数
        int num = 1;
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] >= right) {
                ++num;
                right = intervals[i][1];
            }
        }
        return intervals.size() - num;
    }
};