lc435贪心思路分享

lc 435 Non-overlapping Intervals

首先根据左边界排序所有的array
将第一个array[1]设成右边界，右边界在后面会不断更新
从1开始遍历，每一次都与右边界比较，有两种情况，重叠或者不重叠
一旦重叠，就需要移走一个array，那此时是移走哪一个呢？ 一定是移走右边界更大的那一个array，保留右边界相对小的array，这样才能留出更大的空间放后面的元素。所以需要移走的个数加一，更新右边界。
如果没有重叠，就不需要移走任何一个，只更新右边界。
最后return 个数。
时间复杂度O(nlog(n))
空间复杂度O1

最近在努力攒米到188，求加米米大家～
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            return a[0]-b[0];
        });
        int end = intervals[0][1];
        int res =0;

        for(int i =1; i<intervals.length;i++){
            if(intervals[i][0]<end){
                res++;
                end = Math.min(intervals[i][1], end);
            }else{
                end = intervals[i][1];
            }
        }
        return res;
    }
}

加油加油