LeetCode 435 无重叠区间

LeetCode 435 无重叠区间

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

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

贪心思想

执行用时：5 ms, 在所有 Java 提交中击败了35.16%的用户
内存消耗：40 MB, 在所有 Java 提交中击败了20.16%的用户

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals==null || intervals.length==0 || intervals[0].length==0 || intervals.length==1) {
            return 0;
        }
        /*按照区间右边界升序排序*/
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        /*贪心思想:对于每次选择，总是保证能够获得最大不重叠区间数量*/
        int curr = 0, next = 1;
        int count = 0;
        while(next<intervals.length) {
            /*下一区间next 与 当前区间curr 或 当前区间之前区间 重叠，而 当前区间及之前区间 均不重叠*/
            /*因此要获得最大不重叠区间数量，则需要将下一区间next去除(结果count+1)*/
            if(intervals[next][0]<intervals[curr][1]) {
                count++;
            }
            else {
                curr = next;
            }
            next++;
        }
        return count;
    }
}