刷刷刷 Day 36 | 435. 无重叠区间

435. 无重叠区间

LeetCode题目要求

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

示例

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

解题思路

类似引爆气球一样，处理是否有重叠是，首先应对区间排序，不管是按 start ，还是end 排，都可以。
其中一点需要注意，如果区间A的右界值和区间B的左界值相当，此时不认为是重叠

上代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {

        // 0  1  2  3
        // 1, 2
        //    2, 3
        //       3, 4
        // 1     3
        // 移除 1,3 区间 后
        // 1, 2
        //    2, 3
        //       3, 4
        // 分析， 前区间的 end <= 后区间 start ，认为无重叠
        // 如果前区间的 end > 后区间的 start，认为重叠
        // 

        // 先以区间start左排序？
        Arrays.sort(intervals, (a,b) -> {
            return Integer.compare(a[0], b[0]);
        });

        int removeCount = 0;


        // 首区间的右边界，记录前一区间有边界值
        int pre = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            // 如果上一个区间有边界值 > 当前区间左边界值，说明他们有重合
            if (pre > intervals[i][0]) {
                // 删除的区间数增加，
                removeCount++;
                // 这是取 前一右界值和当前右界值小的，作为下一次的右界值
                pre = Math.min(pre, intervals[i][1]);
            } else {
                // 移动位置
                pre = intervals[i][1];
            }
        }

        return removeCount;
    }
}

附：学习资料链接