java数据结构与算法刷题-----LeetCode435. 无重叠区间

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

文章目录

解题思路：贪心思想。时间复杂度O( $n*log_2n$ )也就是快速排序需要的时间复杂度，空间复杂度O( $log_2n$ )是快速排序需要的栈空间

将所有区间按照第二个字段（end），按照升序排列
依次遍历排序好的区间，并记录当前最大end值
找出不重叠的区间数量，不重叠的条件是：如果当前区间start>=end，那么当前区间和已遍历区间一定不重叠
最后用区间总数 - 不重叠区间 = 需要移除的区间

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            //按照每个区间的end排序，a-b返回值>0 a放在b后面
            public int compare(int[] interval1, int[] interval2) {
                return interval1[1] - interval2[1];//升序排列
            }
        });

        int n = intervals.length;//所有区间的个数
        int right = intervals[0][1];//保存目前重叠区间后最右边界（end）大小。初始保存第一个区间的end
        int ans = 1;//保存有几个不重叠的区间，初始只有第一个区间，一定不重叠
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {//如果当前区间的start >= 目前最右区间大小
                ++ans;//说明当前区间绝对不会重叠
                right = intervals[i][1];//right指向当前区间加入重叠后的end
            }
        }
        return n - ans;//n所有区间 - 非多余区间 = 需要移除的区间
    }
}