题目描述

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

注意:

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

贪心算法介绍:
贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。贪心选择性质简单说就是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。

解题思路:

  1. 首先求出最大不重复区间max
    1. 从区间集合 intvs 中选择一个区间x,这个 x 是在当前所有区间中结束最早的(end 最小)
    2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除
    3. 重复步骤 1 和 2,直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集
  2. 总的区间数length减去最大不重复区间max,length-max即为所求
    static int eraseOverlapIntervals(int[][] intervals) {
        int length = intervals.length;
        int max = maxIntervals(intervals);
        return length - max;
    }

    static int maxIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int count = 1;
        int x_end = intervals[0][1];
        for (int[] interval : intervals) {
            int start = interval[0];
            if (start >= x_end) {
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }

Q.E.D.