题解 | #合并区间#
合并区间
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
/*
HW排序4 合并区间
注意排除输入规模为0和1的情况
*/
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param intervals Interval类vector
* @return Interval类vector
*/
static bool cmp(Interval x,Interval y)
{
return x.start<y.start;
}
vector<Interval> merge(vector<Interval>& intervals) {
// write code here
vector<Interval>v;
if(intervals.size()==0)return v;
if(intervals.size()==1)return intervals;
stable_sort(intervals.begin(),intervals.end(),cmp);
for(int i=0;i<intervals.size()-1;i++){
if(intervals[i].end>=intervals[i+1].start){
intervals[i+1].start=intervals[i].start;
intervals[i+1].end=max(intervals[i].end,intervals[i+1].end);
}else{
v.push_back(intervals[i]);
}
if(i==intervals.size()-2)v.push_back(intervals[i+1]);
}
return v;
}
};