无重叠区间

题目

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

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

具体思路

• 重新按照区间左端点进行排序；
• 如果当前区间和上一区间的左端点重复，count++然后确定选取更小的区间作为上一区间；
• 又或者左端点不重复，那么选取右端点最短的进行选取；

关键点：将原数组先排序（左端点、右端点）

然后计算相邻区间之间的 公共区间 是否存在。如果存在的话，那么就需要去掉这部分。

更新区间：

1. 如果存在公共合理区间：那么不更新区间；
2. 如果不存在公共合理区间：那么将当前的区间设置成 curStart 和 curEnd；

具体代码

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int res = 0;
        sort(intervals.begin(), intervals.end(), cmp);
        for (int i = 1; i < intervals.size(); i++) {
            // 处理区间左端点相同的情况
            if (intervals[i][0] == intervals[i - 1][0]) {
                res++;
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
            }
            // 处理区间部分重叠的其他情况,要用else,否则会重复计算
            else if (intervals[i][0] < intervals[i - 1][1]) {
                res++;
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
            }
        }
        return res;
    }
};

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> {
            return x[0] == y[0] ? x[1] - y[1] : x[0] - y[0];
        });

        int res = 0;
        int curStart = intervals[0][0];
        int curEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            curStart = Math.max(curStart, intervals[i][0]);
            curEnd = Math.min(curEnd, intervals[i][1]);

            if (curStart < curEnd) {
                res++;
            } else {
                curStart = intervals[i][0];
                curEnd = intervals[i][1];
            }
        }
        return res;
    }
}