LeetCode_105_NonOverlappingIntervals

1. question: 无重叠区间（中等）

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/non-overlapping-intervals

示例 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 <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104

2. answers

这道题和引爆气球类似，但是不好转换。还是采用贪心策略比较直观。

首先目的是要删除最小的重叠区间，使得剩余区间互相独立。因为区间数 = 重叠数 + 独立数。所以删除最少的，那么就是独立数最多。

我们是在X轴上放置尽可能多的区间，因此，在放置区间的时候，要保证剩余空间尽可能大，（注意，这里不能优先放置区间范围小的，因为ABC区间，B和AC都重叠，但是B最小，显然这不符合要求）。

那么怎么保证剩余空间尽可能大呢？应该从一侧开始放置，以左侧为例，优先放置右边界小的区间。这样，即使[8, 9]的区间范围小，但是[2, 7]的右边界小，显然剩余的空间更大。

因此，

1. 按照右边界升序排序。
2. 从左向右遍历，判断是否和上一个独立空间重叠，重叠则去掉本元素（计数加1）。
3. 不重叠则更新临近的右边界值。

public class Solution_0105 {

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

        // 按照区间右边界升序排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

        // 存储去掉的区间数量
        int count = 0;

        // 初始化上一个区间边界。
        int edge = Integer.MIN_VALUE;

        for (int i = 0; i < intervals.length; i++) {

            // 若上一个区间的右边界小于当前区间的左边界，说明无交集
            if (edge <= intervals[i][0]) {
                edge = intervals[i][1];
            } else {

                // 有交集，去掉本区间（因为已经按照从小到大排序了，所以右边界肯定大于等于上一个右边界的）
                // 为了保证后续有更多的空间放置区间，所以贪心选择右边界最小的区间，即将本边界去掉。
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println();

        int[][] intervals = {{1,2},{2,3},{3,4},{1,3}};

        Solution_0105 s = new Solution_0105();

        System.out.println(s.eraseOverlapIntervals(intervals));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。