AcWing 803. 区间合并
原题链接
简单
作者:
月下邂逅
,
2024-04-22 14:18:35
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int ,int > pii;
vector <pii> interval,res;
int main()
{
int n,l,r;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&l,&r);
interval.push_back({l,r});
}
sort(interval.begin(),interval.end());//按照左端点排序
int start=-2e9,end=-2e9;
/*for(int i=0;i<n;i++)
{
printf("%d %d\n",interval[i].first,interval[i].second);
}*/
for(auto arr:interval)
{
if(end<arr.first)//如果当前合并区间末尾小于下一个区间末尾,则当前区间无法再合并,保存在res中。并以下一个区间的头和尾开始重新合并
{
if(end!=-2e9)//避免一开始定义的头尾被合并入区间
{
res.push_back({start,end});
}
start=arr.first;
end=arr.second;
}
else//更新当前合并区间末尾
{
end=max(end,arr.second);
}
}
res.push_back({start,end});//加入最后一个区间
printf("%d",res.size());
return 0;
}