AcWing 803. 区间合并
原题链接
简单
作者:
._5144
,
2023-11-16 23:24:05
,
所有人可见
,
阅读 45
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;
vector<pair<int,int>> segs;
void merge(vector<pair<int,int>> &segs)
{
vector<pair<int,int>> res;
// 要先排序
sort(segs.begin(),segs.end());
int st = -2e9,ed = -2e9; // 维护区间的初始左右端点
for(auto seg : segs) // 枚举所有区间
{
if(ed < seg.first) // 当前维护区间与枚举区间没有交集
{
if(st != -2e9)
res.push_back({st,ed});
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;
for(int i = 0; i < n; i ++)
{
int l,r;
scanf("%d%d",&l,&r);
segs.push_back({l,r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}