无重叠区间

问题陈述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

1
2
3
4
5
输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

思路分析

算法思路：

  1. 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
  2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
  3. 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int intevalSchedual(int[][] intvs){
    if(intvs.length==0) return 0;
    //对intvs按区间end升序排列
    Arrays.sort(intvs,new Comparator<int[]>(){
        public int compare(int[] a,int[] b){
            return a[1]-b[1];
        }
    });
    //至少会有一个区间不相交
    int count=1;
    int x_end=intvs[0][1];
    for(int[] inteval:intvs){
        int start=inteval[0];
        if(start>=x_end){
            count++;
            x_end=inteval[1];
        }
    }
    return intvs.length-count;
}