2022.04.21(LC_435_无重叠区间)

方法：贪心

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //按右端点升序排列
        Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
        int ans = 0;
        int pos = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            //找到互不重叠的区间，并不断更新最小的右端点
            if (intervals[i][0] >= pos) {
                pos = intervals[i][1];
            //需要移除的重叠区间
            } else {
                ans++;
            }
        }
        return ans;
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];
            }
        });
        int pos= intervals[0][1];
        int ans = 1;
        for (int i = 1; i < intervals.length; i++) {
            //需要保留的区间
            if (intervals[i][0] >= pos) {
                ans++;
                pos= intervals[i][1];
            }
        }
        //区间总数减去需要保留的区间，即为需要移除的区间
        return intervals.length - ans;
    }
}