题目描述

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

注意:

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.