无重叠区间

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，435. Non-overlapping Intervals

先看题目描述

rXyxu8.png

大意就是给定一个数组 intetvals 代表多个时间区间的集合，问要让时间区间没有重叠，最少需要删除多少个时间区间

算法和思路

看到这题是有关区间的，很容易就想到以前在算法课上学过的区间调度问题，想到可以用贪心算法解决类似问题

贪心算法

贪心策略是：

  • 每次从区间集合中选出结束时间最早的区间 x
  • 将与 x 相交的区间从区间集合中删除

具体到实现上，因为每次都要从集合中选出结束时间最早的区间，我们可以先将区间按照结束时间升序排列，首先以第一个区间作为当前选中的区间，然后按顺序遍历区间集合，对于当前选中的区间 x，我们将与 x 相交的区间从集合中删除，由于区间已按结束时间升序排列，我们只需比较当前遍历的区间的开始时间与 x 的结束时间即可。若当前遍历的区间的开始时间小于 x 的结束时间，说明该区间与 x 相交，将该区间删除，转而用下一个区间与 x 比较；否则，说明当前遍历的区间与 x 不相交，则将当前遍历的区间作为当前选中的区间 x。遍历完后返回删除的区间数量即可

算法源码

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) {
        int len = intervals.length;
        if (len <= 1) {
            return 0;
        }
        int res = -1;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] == o2[1] ?  o2[0] - o1[0] : o1[1] - o2[1];
            }
        });
        int preEnd = intervals[0][1];
        for (int[] interval : intervals) {
            if (interval[0] < preEnd) {
                res++;
            } else {
                preEnd = interval[1];
            }
        }
        return res;
    }
}