一、题目简述
给定一些区间，找到需要移除的最小区间数，以使剩余的区间之间没有重叠。 注意：
区间的终点总是大于起点如同
[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 解释：区间不重叠无需移除
二、编程思路
本题目的编程思路与“参加最多会议数”的思路相同，给定一系列会议的起点与终点，能够参加最多的会议，就是不参加最少的会议，且剩余的会议之间互不重叠。 因此，首先对Interval根据结束时间进行排序，排序原则：
结束时间早的在前结束时间相同，开始时间晚的在前
之后使用贪心算法，每次选择与当前已选择的区间不重叠的区间。若重叠，则记录移除区间数的
eraseNum++
，若不重叠，将当前区间纳入已选择。
三、程序设计
/**
* Definition
for an interval.
* struct Interval {
*
int start;
*
int end;
* Interval() : start(
0),
end(
0) {}
* Interval(
int s,
int e) : start(s),
end(e) {}
* };
*/
bool cmp(Interval in1,Interval in2){
if(in1.
end!=in2.
end){
return in1.
end<in2.
end;
}
else{
return in1.start<in2.start;
}
}
class Solution {
public:
int eraseOverlapIntervals(vector<Interval>& intervals) {
if(intervals.size()==
0) return
0;
sort(intervals.begin(),intervals.
end(),cmp);
/*
for(
int i=
0;i<intervals.size();i++){
cout<<intervals[i].start<<
" "<<intervals[i].
end<<endl;
}*/
int eraseNum=
0;
int endTime=intervals[
0].
end;
for(
int i=
1;i<intervals.size();i++){
if(intervals[i].start>=endTime){
endTime=intervals[i].
end;
}
else{
eraseNum++;
}
}
return eraseNum;
}
};
四、编程心得
学会对问题进行适当转化。
转载请注明原文地址: https://ju.6miu.com/read-9736.html
