区间重叠问题

区间未重叠数量计算：

class Solution {
    public int findMinArrowShots(int[][] points) {
        //需要用第一种比较器？第二种会报错，在涉及数的大小边界的时候
        Arrays.sort(points,(a, b) -> Integer.compare(a[0], b[0]));
        //(a, b) -> Integer.compare(a[0], b[0])
        //(p1,p2)->(p1[0]-p2[0])
        int count=1;
        for(int i=1;i<points.length;i++){
            if(points[i][0]>points[i-1][1]){//如果区间未重叠
                count++;//未重叠区间数量+1
            }else{
                points[i][1]=Math.min(points[i][1],points[i-1][1]);//更新最小的区间的右边界
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

先计算出所有非重叠区间数量，然后只要把判断条件加个等号（认为[0，1][1，2]不是相邻区间），然后用总区间数减去非重叠区间数量 就是要移除的区间数量了。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(p1,p2)->Integer.compare(p1[0],p2[0]));
        int count=1;
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]>=intervals[i-1][1]){//如果区间未重叠
                count++;//未重叠区间数量+1
            }else{
                intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);//更新最小的区间的右边界
            }
        }
        return intervals.length-count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14