【每日算法Day 79】最多不重叠的区间数量
Wallace Xu 2020-08-18 贪心
# LeetCode 435. 无重叠区间 (opens new window)
# 题目描述
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
# 示例
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
1
2
3
2
3
# 解题思路
使用贪心思想，将这些区间按照结束时间进行排序，处理时将开始值小于上一个区间lastInterval结尾值得区间排除（因为如果这些区间中某一个构成了最多无重叠区间，那么lastInterval也一定能构成最多无重叠区间，所以可以排除这些区间），遇到开始值大于lastInterval结束值得区间则计数+1，更新lastInterval。
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 1, lastEnd = intervals[0][1];
for (int[] interval : intervals) {
if (interval[0] >= lastEnd) {
count++;
lastEnd = interval[1];
}
}
return intervals.length - count;
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
时间复杂度为O(nlogn+n)=O(nlogn)，n为输入得区间数量。
另外LeetCode 452.用最少数量的箭引爆气球 (opens new window)和本题非常类似，唯一不同在于如果一个区间的首边界和另一个区间的尾边界相同，那么视为重叠的区间。