435. 无重叠区间 - Java+Kotlin 贪心算法

原题地址：https://leetcode.cn/problems/non-overlapping-intervals/

题解

参考题解思路

我们将最终版本的区间集合视作一个List或Queue，而我们的目标是：不断地向List中插入符合条件的区间

对于一个空List，我们思考如何往里添加第一个元素，我们并不在意这个区间的左边界，而是这个区间的右边界，为了向List里加入尽可能多的元素，考虑到List[i]的左区间必然小于List[i-1]的右区间，我们选择一个右边界尽可能小的区间，这样能为后续的插入预留出更多的空间

我们对intervals按照区间的右边界升序排序

当往里插入了一些区间后，我们只需要按顺序遍历intervals，由于intervals已经按照右边界升序排序，只要遍历到一个满足左边界小于List中最后一个区间的右边界（用一个start维护）的区间，这个区间必然是满足条件的所有区间的最优解，直接将其插入List，然后维护start变量即可

最后对于List的size就是无重叠区间的最大数量，用intervals.size减去这个值就是我们需要的答案

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt((int[] a) -> a[1]));
        int start=Integer.MIN_VALUE;
        int cnt=0;
        for (int i=0;i<intervals.length;i++){
            if(intervals[i][0]>=start){
                start=intervals[i][1];
                cnt++;
            }
        }
        return intervals.length-cnt;
    }
}

class Solution {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        intervals.sortBy{ it[1] }
        var start=Int.MIN_VALUE
        var cnt=0
        for(i in 0 until intervals.size){
            if(intervals[i][0]>=start){
                start=intervals[i][1]
                cnt++
            }
        }
        return intervals.size-cnt
    }
}