435.无重叠区间

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

注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。例如 [1, 4] 和 [2, 5] 是不重叠的

思路

  • 改为计算最多可以选多少个互不重叠的区间，那么没选的区间就是要移除的区间。
  • 对第二个元素进行升序排序
  • 第一个范围肯定是能选的
  • 贪心选择，右侧尽量小的范围
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->a[1]-b[1]);
        int pre=Integer.MIN_VALUE; //确保选取第一个范围
        int ans=0;
        for(int[] nums:intervals){
            if(pre<=nums[0]){
                ans++;
                pre=nums[1];	//更新左侧边界
            }
        }
        return intervals.length-ans;
    }
}