思路
如果我们按照区间的左端点排序,那么在排完序的列表中,可以合并的区间一定是连续的。
排序后,前一个线段的左端点小于等于当前线段的左端点,再根据当前线段的右点是否大于前一个线段的左点,来判断是否能够合并。
独立代码-结构体版
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
struct node{
int l,r;
node(int x,int y):l(x),r(y){}
node(){}
};
vector<node> a,mer;
bool cmp(node &a,node &b){
return a.l<b.l;
}
void merge(){
sort(a.begin(),a.end(),cmp);
for(int i=0;i<n;i++){
int L=a[i].l,R=a[i].r;
if(!mer.size()||mer.back().r<L){
mer.push_back(node(L,R));
}
else{
mer.back().r=max(mer.back().r,R);
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
a.push_back(node(x,y));
}
merge();
for(int i=0;i<mer.size();i++){
printf("%d,%d ",mer[i].l,mer[i].r);
}
printf("\n");
return 0;
}
力扣版
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==0) return {};
vector<vector<int>> merged;
sort(intervals.begin(),intervals.end());
for(int i=0;i<intervals.size();i++){
int L=intervals[i][0],R=intervals[i][1];
if(!merged.size() || merged.back()[1]<L){
merged.push_back({L,R});
}
else{
merged.back()[1]=max(merged.back()[1],R);
}
}
return merged;
}
};