无重叠区间

发表于 分类于 阅读次数：

无重叠区间（难度：中等）

1

转自：

作者：labuladong 链接：https://leetcode-cn.com/problems/non-overlapping-intervals/solution/tan-xin-suan-fa-zhi-qu-jian-diao-du-wen-ti-by-labu/ 来源：力扣（LeetCode）

本文解决一个很经典的贪心算法问题 Interval Scheduling（区间调度问题）。给你很多形如 [start, end]的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。 举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。

这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，请问你今天最多能参加几个活动呢？显然你一个人不能同时参加两个活动，所以说这个问题就是求这些时间区间的最大不相交子集。

方法：贪心算法

思路
  1. 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
  2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
  3. 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。
1
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        
		// 按区间的end升序排列
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[1] - b[1];
            }
        });

        int count = 1;
        int x_end = intervals[0][1];
        for(int[] intv:intervals){
            int start = intv[0];
            if(x_end <= start){
                count++;
                x_end = intv[1];
            }
        }
        return intervals.length - count;
    }
}
复杂度

时间复杂度：O(nlogn). 排序需要O(nlogn)的时间。

空间复杂度：O(1). 不需要额外空间。

2