Leetcode 435 无重叠区间

题意理解：

????????给定一个区间的集合 intervals

? ? ? ? 要求需要移除区间，使剩余区间互不重叠?

? ? ? ? 目标：最少需要移除几个区间。

解题思路：

? ? ? ? 采用贪心思路解题，什么是全局最优解，什么是局部最优解。

? ? ? ? 全局最优解，删除最少的区间，使剩下的区间不重叠。

? ? ? ? 局部最优：尽可能识别重叠的区域，并移除相应区间。

? ? ? ? 为了方便识别重叠区间，我们以区间的左边界为准升序排列，左区间一致，以右区间升序排列。

? ? ? ? 最终的序列：同起点的区间，小区间总在最前面。

? ? ? ? 当第i个区间的左边界<第i-1个区间的右边界时，出现重叠区域，需要删除的count++;

? ? ? ? 当删除该区间后，第i+1个元素的左边界和最早截止的区间的右边界比较，以保证更多的不重叠区间。

? ? ? ? 为了方便统一处理，当记录删除一个区间时:

????????????????将要删除第i的区间右边界设为Math.min(第i-1区间的右边界,第i个区间的右边界)

????????

????????

1.贪心解题

我们使用count记录发生重叠要删除的区域。

    public int eraseOverlapIntervals(int[][] intervals) {
        int count=0;
        //对区间进行排序
        Arrays.sort(intervals,(o1,o2)->(o1[0] - o2[0]));
        //遍历区间,总是和最左边的区间比较
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<intervals[i-1][1]){//有重叠
                count++;
                intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
            }
            //无重叠，不操作
        }
        return count;
    }

2.分析

时间复杂度：O(n logn) 排序所需时间O(nlogn)+遍历的时间O(n)

空间复杂度：O(logn) 排序所需的额外栈空间O(logn)

n为输入数组的大小