435. 无重叠区间

题目：

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

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-overlapping-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例：

image.png

思路：

贪心算法
用总区间数减去不重复的区间数；
首先，使用到一个排序二维数组的方法：根据第二列的数值排序

Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

然后每次选出区间终点最小的，并且不会重复的区间；
上面已经将数组按终点大小排序好，所以只需要按顺序遍历，即为每次选出区间终点最小的；
而重复的区间，即：该区间的起点小于上一个区间的终点；
如果是重复区间，就继续遍历下一个区间；
如果不是重复区间，就将该区间的终点设为整个区间的终点，然后不重复区间个数加一；
直到所有区间遍历完成。

代码：

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length ==0) return 0;
        //按照区间终点大小排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        //不重叠的区间个数
        int count = 1;
        //第一个区间的终点
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            //判断下一个区间的起点是否小于上一个区间的终点
            //如果是，证明是重叠区间，就继续遍历下一个区间
            if (intervals[i][0] < end) {
                continue;
            }
            //如果不小于，就证明不是重叠区间
            //就将新区间的终点赋给end
            end = intervals[i][1];
            //不重叠的区间数加一
            count ++;
        }
        //总区间数减去不重复的区间数；
        return intervals.length - count;
    }
}

时间复杂度：O(n)，空间复杂度：O(1)

最后编辑于：2019.10.28 16:54:40