一、题目简述
给定一些区间,找到需要移除的最小区间数,以使剩余的区间之间没有重叠。 注意:
区间的终点总是大于起点如同
[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