Week2-Day4 ##排序##
合并区间
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
我们将区间按左区间进行排序,然后比较l区间和r区间是否存在交集
当存在交集时,我们更新当前l区间的end值,直到区间不存在交集。
循环结束说明已经完成了一个区间的合并,我们将此时l区间存下来,并把l移动到r的位置开始下一个区间的合并
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param intervals Interval类vector
* @return Interval类vector
*/
vector<Interval> merge(vector<Interval>& intervals) {
int l=0,r=0;
vector<Interval>ans;
//按照左区间排序,相同时排序较小的右区间
sort(intervals.begin(),intervals.end(),[&](Interval&i,Interval&j){
return i.start == j.start? i.end < j.end : i.start < j.start;
});
int n=intervals.size();
while(r<n){
//合并区间有交集的
while(r<n && intervals[r].start <= intervals[l].end ){
intervals[l].end=max(intervals[l].end,intervals[r].end);
r++;
}
ans.push_back(intervals[l]);
l=r;
}
return ans;
}
};
周周打卡图粘贴处
#和牛牛一起刷题打卡#