给定一个区间的集合 intervals
,其中 intervals[i] = [starti, endi]
。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
示例1:
首先呢,既然题目给定的N个区间中,我们假设肯定有重叠的部分,那么我们怎么去判断某一部分的区间是重叠的呢?那肯定是需要比较相邻两个区间的左右边界。更重要的是,我们需要对给定的区间做一个排序。以便于比较。
那么如何做到减少最少数量的区间以达到题目要求?
核心思想:尽可能保证每个区间的范围越小越好。那么重叠的概率也就越小。
那么排序的时候这就需要分两种情况来考虑。
思路一:按照右边界来排序。那么我们应该从左往右进行遍历。那么右边界越小越好(局部最优)。右边界越小,留给下一个区间的范围可能就越大。存在交集的可能越小。那么需要删除的区间个数越少。(全局最优)
思路二:按照左边界来排序。那么我们应该从右往左进行遍历。那么左边界越大越好。左边界越大,留给上一个区间的范围可能就越大。
以右边界排序为例,如图:
我画了6个区间:分别进行了标号。也能看出来根据右边界进行排序。
那么遍历的过程中计入存在交集的个数,即是最终要删除的个数。
以按照右边界排序为例,最终结果:
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;
}