Leetcode 435. 无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
- 输入: [ [1,2], [2,3], [3,4], [1,3] ]
- 输出: 1
- 解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
- 输入: [ [1,2], [1,2], [1,2] ]
- 输出: 2
- 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
- 输入: [ [1,2], [2,3] ]
- 输出: 0
- 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
解题思路：
这道题跟我们上题的 Leetcode 452. 用最少数量的箭引爆气球基本一样。
首先对数组进行一个排序，接着从第二个区间开始遍历该数组，如果intervals[i-1][1] > intervals[i][0],说明有重叠！！result加一就行。但是这里有个小坑就是，我们在每次遇到重叠的时候，需要对这两个区间重叠部分的第二个元素进行比较拿到最小的结果。
例如：[ [1,2], [1,3], [2,3], [3,4] ]
当首次遍历[1,2]和[1,3]，这时候比较完result++，接着我们需要把[1,2]中的2和[1,3]中的3进行比较，并且更新2到第二个区间，更新完也就是 [ [1,2], [1,2], [2,3], [3,4] ],否则我们会多计算一次重叠，因为我们按道理是把[1,3]去掉了，所以我们要更新[1,3]为[1,2]。
下面看具体的解题步骤：
- 初始化一个变量 result，表示需要移除的区间数量，默认为0。
- 使用 Arrays.sort 方法对区间数组进行排序，排序的比较规则是首先按照区间的起始节点进行升序排序，如果起始节点相同，则按照结束节点进行升序排序。
这样的排序方式可以确保在选择区间时，结束节点较早的区间优先考虑。 - 初始化一个变量 temp，表示当前选择的区间的结束节点
- 初始值为第一个区间的结束节点 intervals[0][1]
- 从第二个区间开始，遍历排序后的区间数组，对于每个区间 intervals[i]，执行以下步骤：
a. 如果 temp 大于 intervals[i][0]，说明当前区间与前一个选择的区间重叠，需要移除一个区间。
在这种情况下，选择移除当前区间，即 result 加1。
b. 如果 temp 小于等于 intervals[i][0]，说明当前区间与前一个选择的区间不重叠，可以选择该区间。
更新 temp 为 intervals[i][1]，表示当前选择的区间的结束节点。 - 遍历结束后，返回 result，即需要移除的区间数量。
代码实现：
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals == null || intervals.length == 0){
return 0;
}
int result = 0;
Arrays.sort(intervals,(o1,o2)->{
if(o1[0] == o2[0]){
return o1[1] - o2[1];
}else{
return o1[0] - o2[0];
}
});
int temp = intervals[0][1];
for(int i = 1; i < intervals.length;i++){
if(temp > intervals[i][0]){
result++;
temp = Math.min(temp, intervals[i][1]);
}else{
temp = intervals[i][1];
}
}
return result;
}
}
优化：
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals == null || intervals.length == 0){
return 0;
}
int result = 0;
Arrays.sort(intervals,(o1,o2)->{
if(o1[0] == o2[0]){
return o1[1] - o2[1];
}else{
return o1[0] - o2[0];
}
});
// int temp = intervals[0][1];
for(int i = 1; i < intervals.length;i++){
if(intervals[i-1][1] > intervals[i][0]){
result++;
intervals[i][1] = Math.min(intervals[i-1][1], intervals[i][1]);
}else{
continue;
}
}
return result;
}
}
其实我们根本不用声明一个temp，直接把当前区间中结束节点更新成最小的就行～
评论区