803区间合并
给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
算法一:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
struct st
{
int l,r;
}p[N];
int n;
int cmp(st a,st b)
{
return a.l<b.l;
}
int main()
{
cin>>n;
for(int i=0;i<n;++i) cin>>p[i].l>>p[i].r;
sort(p,p+n,cmp);
int ans=1;
int d=p[0].r;
for(int i=1;i<n;++i)
{
if(p[i].l>d) {
ans++;
d=p[i].r;
}
else
{
if(d<p[i].r)
d=p[i].r;
}
}
printf("%d\n",ans);
}
算法二:
视频版,大同小异
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<PII> p,res;
const int N=100010;
int n;
void merge()
{
int l=p[0].first,r=p[0].second;
res.push_back({l,r});
for(int i=1;i<n;++i)
{
if(r<p[i].first)
{
l=p[i].first;r=p[i].second;
res.push_back({l,r});
}
else r=max(r,p[i].second);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;++i)
{
int l,r;
cin>>l>>r;
p.push_back({l,r});
}
sort(p.begin(),p.end());
merge();
cout<<res.size()<<endl;
}