题目描述

解题思路

如果按照左边界排序，还从左向右遍历的话，其实也可以，逻辑会有所不同。
一些同学做这道题目可能真的去模拟去重复区间的行为，这是比较麻烦的，还要去删除区间。
题目只是要求移除区间的个数，没有必要去真实的模拟删除区间！
我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。
局部最优推出全局最优，试试贪心！
这里记录非交叉区间的个数还是有技巧的，如图：
区间，1，2，3，4，5，6都按照右边界排好序。
每次取非交叉区间的时候，都是可右边界最小的来做分割点（这样留给下一个区间的空间就越大），所以第一条分割线就是区间1结束的位置。
接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘已经是按照右边界排序的了。
区间4结束之后，在找到区间6，所以一共记录非交叉区间的个数是三个。
总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[1], o2[1]));    // 按照右区间进行排序
    int end = intervals[0][1];// 记录区间分割点
    int count = 1;// 记录非交叉的区间个数
    for (int i = 1; i < intervals.length; i++) {
        if (end <= intervals[i][0]) {   // 两个区间挨着算作未交叉
            end = intervals[i][1];
            count++;    // 区间未交叉的个数加一
        }
    }
    return intervals.length - count;    // 总数减去未交叉的区间数等于交叉的区间数
}