AlgoPressAppearance
0435-无重叠区间
https://leetcode.cn/problems/non-overlapping-intervals
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
- 可以认为区间的终点总是大于它的起点。
- 区间 [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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
思路1【错误】
- 排序，按照起点排序
- 找出最大重叠数，就是要移除的空间数减1 : 该方法有问题 [[0,2],[1,3],[2,4],[3,5],[4,6]] 返回1， 应该返回2
这个方法缺少了对前面区间所有可能的判断，需要取最大值
注意：按照右节点排序就没有前面curMax的问题了
参考代码
csharp
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
int left = 0;
int right = 0;
for(int i=0; i<intervals.Length; i++){
right = Math.Max(intervals[i][1]);
}
int max = 0;
int curMax = 0;
//在每个点检查点线段是否包含该点
for(int i = left; i<=right; i++){
curMax = 0;
for(int j = 0; j<intervals.Length; j++){
if(intervals[j][0] <= i && intervals[j][1] > i){
curMax++;
}
}
max = Math.Max(max,curMax);
}
return max-1;
}
}
思路2：动态规划【官方】
转化题目为：选出最多数量的区间，使得他们互相不重叠，然后用总数量 减去 该数量，就是结果。 求最多数量的区间，使用动态规划
定义dp, dp[i]表示第i个区间，能挑选出最多数量的区间， dp[i] = max(dp[j]: 当 intervals[i][0] > intervals[j][1])+1
参考代码
csharp
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
//排序
Array.Sort(intervals, (p1,p2) =>{
if(p1[0] > p2[0]){
return 1;
}
else if(p1[0] < p2[0]){
return -1;
}
else{
return 0;
}
});
int[] dp = new int[intervals.Length];
//默认都是包含至少一个区间，填1
for(int i=0; i<dp.Length; i++){
dp[i] = 1;
}
int max = 1;
for(int i=1; i<intervals.Length; i++){
//因为 dp[i] 要取前面所有满足条件的最大值，所以循环j至i
for(int j=0; j<i; j++){
//当第i个区间的左边界大于第j个区间的右边界，我们就可以将此加1
if(intervals[i][0] >= intervals[j][1]){
dp[i] = Math.Max(dp[i],dp[j]+1);
max = Math.Max(dp[i],max);
}
}
}
return intervals.Length - max;
}
}
思路3：贪心
首先同样转化问题：找寻不重复的最大线段数
贪心算法，按照起点排序：选择结尾最短的，后面才可能连接更多的区间（如果两个区间有重叠，应该保留结尾小的） 把问题转化为最多能保留多少个区间，使他们互不重复，则按照终点排序，每个区间的结尾很重要，结尾越小，则后面越有可能容纳更多的区间。
将线段按照右端点顺序排列，循环线段，设置right 为第一个线段的最右端，因为大家都是按照右端排列的，所以当下一个线段的左端 >= 当前的最右的时候。 可选择线段+1，将 right 更新为当前线段的右端，继续循环
参考代码
csharp
public class Solution{
public int EraseOverlapIntervals(int[][] intervals){
//按右端排序
Array.Sort(intervals, (p1,p2)=>{
return p1[1].CompareTo(p2[1]);
});
//取得第一个线段的边界
int right = intervals[0][1];
int max = 1;
int n = intervals.Length;
for(int i=1; i<n; i++){
if(intervals[i][0] >= right){
max++;
right = intervals[i][1];
}
}
//返回可删除的线段
return n-max;
}
}
csharp
public class Solution{
public int EraseOverlapIntervals(int[][] intervals){
//按左端排序
Array.Sort(intervals, (p1,p2)=>{
return p1[1].CompareTo(p2[1]);
});
//取得第一个线段的右边界
int right = intervals[0][1];
int max = 1;
int n = intervals.Length;
for(int i=1; i<n; i++){
if(intervals[i][0] >= right){
max++;
right = intervals[i][1];
}
else{
//注意这里按照左边界排序的话，就必须取min(right)，因为后面的线段的右边界可能小于左边界
right = Math.Min(intervals[i][1],right);
}
}
//返回可删除的线段
return n-max;
}
}
复习贪心【ME】：20220514
csharp
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
//思路，按照右边界排序，右边接相同的时候按左边降序排序，这样优先删除大的，尽量保留小的
Array.Sort(intervals, (a,b)=>{
if(a[1] != b[1]){
return a[1].CompareTo(b[1]);
}
else{
return b[0].CompareTo(a[0]);
}
});
//循环，发现重叠则扣减，发现超过第一个范围，则调整 left 和 right
int left = intervals[0][0];
int right = intervals[0][1];
int remove = 0;
for(int i=1; i<intervals.Length; i++){
if(intervals[i][0] < right){
remove++;
}
else{
left = intervals[i][0];
right = intervals[i][1];
}
}
return remove;
}
}
优化：其实上面按照右边界排序即可。
csharp
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
//按照右边界排序
Array.Sort(intervals, (a,b)=>{
return a[1].CompareTo(b[1]);
});
//循环，发现重叠则扣减，发现超过第一个范围，则调整 left 和 right
int left = intervals[0][0];
int right = intervals[0][1];
int remove = 0;
for(int i=1; i<intervals.Length; i++){
if(intervals[i][0] < right){
remove++;
}
else{
left = intervals[i][0];
right = intervals[i][1];
}
}
return remove;
}
}
复习:20220622
csharp
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
//按照左边界排序也可以
Array.Sort(intervals,(a,b)=>{
return a[0].CompareTo(b[0]);
});
//找出重叠的个数
int count = 0;
int right = intervals[0][1];
for(int i=1; i<intervals.Length; i++){
if(intervals[i][0]<right){
count++;
right = Math.Min(right,intervals[i][1]); //左边界排序注意要缩短对应的右边界
}
else{
right = intervals[i][1];
}
}
return count;
}
}