算法基础课复习第三天<区间合并>
作者:
骏杰
,
2022-04-30 16:43:59
,
所有人可见
,
阅读 192
//(1,3),(2,6)可以合并为(1,6)
//用vector,和pair存储区间的两个端点
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
const int N=100010;
typedef pair<int, int> PII;
vector<PII> segs;//区间
void merge(vector<PII> &segs)//一定要加&
{
vector<PII> res;//合并后的区间
sort(segs.begin(),segs.end());
int st=-2e9,ed=-2e9;//左右边界初始定义,两个都是-的,如果右边为2e9则ed<segs.first就运行不出
for(auto seg:segs)//遍历每一个区间seg
{
if(ed<seg.x)
{
if(st!=-2e9)//必须加不然容易把(-2e9,2e9)加进来
{
res.push_back({st,ed});
}
st=seg.x;
ed=seg.y;//必须写在外面
}
else ed=max(ed,seg.y);//如果右边界大
}
if(st!=-2e9) res.push_back({st,ed});
segs=res;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
merge(segs);
cout<<segs.size()<<endl;//这里一个区间相当于一个元素
return 0;
}
这么拼命给谁看呐
give me!
那就在拼一点儿, 我看好你
肝!