想要精通算法和SQL的成长之路 - 无重叠区间
- 前言
- 一. 无重叠区间
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 无重叠区间
原题链接
给定一个区间的集合 intervals
,其中 intervals[i] = [starti, endi]
。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
示例1:
- 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
- 输出: 1
- 解释: 移除 [1,3] 后,剩下的区间没有重叠。
首先呢,既然题目给定的N个区间中,我们假设肯定有重叠的部分,那么我们怎么去判断某一部分的区间是重叠的呢?那肯定是需要比较相邻两个区间的左右边界。更重要的是,我们需要对给定的区间做一个排序。以便于比较。
那么如何做到减少最少数量的区间以达到题目要求?
核心思想:尽可能保证每个区间的范围越小越好。那么重叠的概率也就越小。
那么排序的时候这就需要分两种情况来考虑。
思路一:按照右边界来排序。那么我们应该从左往右进行遍历。那么右边界越小越好(局部最优)。右边界越小,留给下一个区间的范围可能就越大。存在交集的可能越小。那么需要删除的区间个数越少。(全局最优)
思路二:按照左边界来排序。那么我们应该从右往左进行遍历。那么左边界越大越好。左边界越大,留给上一个区间的范围可能就越大。
以右边界排序为例,如图:
我画了6个区间:分别进行了标号。也能看出来根据右边界进行排序。
- 第二个区间和第三个区间都和黄色虚线位置存在交集,那么这两个区间应该被删除。
- 找到第一个与黄色虚线不存在交集的区间,它的右边界作为新的交际线。也就是区间4。
- 同理,第一个和区间4不存在交集的也就是区间6。区间5存在交集。
那么遍历的过程中计入存在交集的个数,即是最终要删除的个数。
以按照右边界排序为例,最终结果:
public int eraseOverlapIntervals(int[][] intervals) {// 根据右边界从小到大排序Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);int count = 0;int pre = Integer.MIN_VALUE;// 从左往右遍历,希望右边界越小越好for (int i = 0; i < intervals.length; i++) {// 上一个右边界(没有重复的) > 当前区间的左边界, 说明当前区间出现交集if (pre > intervals[i][0]) {// 记录交集的个数,也就是要删除的区间个数count++;} else {// 更新右边界pre = intervals[i][1];}}return count;
}