区间合并

8.区间合并

**主要思想：**给定很多个区间，若2个区间有交集，将二者合并成一个区间

• 先按照区间的左端点进行排序
• 然后遍历每个区间，根据不同情况进行合并，对于两个区间（后一个区间为i）可能有下面几种关系：

• 对于第一种情况，区间不变
• 对于第二种情况，end要变成区间i的右端点
  • 前面两种情况，可以合并为将end更新为end和区间i的右端点中的较大者
• 对于第三种情况，将当前维护的区间加入答案，并将维护的区间更新为区间i

Acwing 803.区间合并

实现思路：

• 先读入区间端点(l,r)，将其存入segs数组内，再设置一个结果数组res
• 将segs数组排序好，设置左右端点（st,ed）为第一个维护的区间，初始都为负无穷大
• 依次取出segs数组中的元素，比较当前区间（维护区间）ed和另一个区间seg的l关系，如果ed<l，叫说明两个区间没有交集，则直接将seg加入res中，并将待维护的区间变为seg（即后移，设置新的维护区间）。反之，更新ed为最大值（因为区间排好序，所以不用将st更新为最小）。
• 最后判断segs是否为空，若不为空，则将最后剩余一个维护的区间加入res中。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef pair<int,int> PII;
vector<PII> segs;
int n;
 
void merge(vector<PII> &segs){
    vector<PII> res;//设置一个结果数组
    int st=-2e9,ed=-2e9;//用-2*10^9代表负无穷
    for(auto seg:segs){
        if(ed<seg.first){//当前维护区间与下一个区间无交集
            if(st!=-2e9) res.push_back(seg);//判断初始化区间负无穷
            st=seg.first,ed=seg.second;//后移，更新维护区间
        }else ed=max(ed,seg.second);//有交集，取两个区间的右端点最大值
    }
    if(st!=-2e9) res.push_back({st,ed});//判断，然后将剩下的区间加入结果
    segs=res;
}
 
int main() {
    cin>>n;
    while(n--)
    {
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
     //先对区间按左端点排序
    sort(segs.begin(),segs.end());//sort自动对pair先按左端点排序，再按右端点排序
    merge(segs);
    cout<<segs.size();
    return 0;
}