无重叠区间 中等🌟🌟🌟🌟
课后作业
问题描述
原文链接：435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104
代码实现
Java
class Solution {
/*
转化问题：保存最大的区间数量，使得区间不重叠，比如最大数间数量为max，
return 数组长度 - max。
intervals = [,[3,4], ];
怎么选择：我们要选择右边界比较小的区间
[1,2],[2,3]，[3,4]
步骤：
对数组排序，要以第二个元素来排序
之后遍历数组，如果遇到不重叠的就选下来
*/
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length <= 1) return 0;
//排序
Arrays.sort(intervals, new Comparator<int[]>(){
//重写compare
public int compare(int[] s1, int[] s2){
return s1[1] - s2[1];
}
});
//
int max = 1;
int right = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] >= right){
max++;
right = intervals[i][1];
}
}
return intervals.length - max;
}
}
Python
class Solution:
def eraseOverlapIntervals(self, intervals):
if len(intervals) <= 1:
return 0
intervals.sort(key=lambda x: x[1])
max_count = 1
right = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] >= right:
max_count += 1
right = intervals[i][1]
return len(intervals) - max_count
C++
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.size() <= 1) {
return 0;
}
// 排序
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int max_count = 1;
int right = intervals[0][1];
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= right) {
max_count++;
right = intervals[i][1];
}
}
return intervals.size() - max_count;
}
};
Go
import "sort"
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) <= 1 {
return 0
}
// 排序
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
maxCount := 1
right := intervals[0][1]
for i := 1; i < len(intervals); i++ {
if intervals[i][0] >= right {
maxCount++
right = intervals[i][1]
}
}
return len(intervals) - maxCount
}