题解 P2434 【[SDOI2005]区间】
顾z
2018-09-01 19:14:13
**题目描述**
给定n个区间,求满足给定条件的不相交闭区间。
条件:两个区间[a, b]和[c, d]是按照升序排列的,那么我们有a<=b<c<=d。
## 广告 [安利博客](https://87960.blog.luogu.org/#)
**分析:**
~~题目不用概括了吧...~~
所以说,我们可以将区间按照升序排序,然后更新区间左右端点,左端点取最靠左的,右端点取最靠右的。
至于为什么是正确的?~~(尝试说一下~~
我们去将相交区间合并,因为这样我们可以得到相交区间所覆盖最大的区间,而这样,如果我们枚举过程中遇到一个区间的左端点大于当前区间的右端点,我们就可以输出当前的区间,然后更新左右端点,继续去求下一个满足条件的区间。
然后根据这种思想去实现即可.
记得输出最后一次的答案.
-----------------------代码------------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
IL void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n;
struct cod{int l,r;}qujian[50008];//区间
IL bool ccp(const cod&a,const cod&b){return a.l<b.l;}
int main()
{
read(n);
for(RI i=1;i<=n;i++)
read(qujian[i].l),read(qujian[i].r);
std::sort(qujian+1,qujian+n+1,ccp);
int le=qujian[1].l,re=qujian[1].r;
for(RI i=2;i<=n;i++)
{
if(re<qujian[i].l)
{
printf("%d %d\n",le,re);
le=qujian[i].l;
}
le=std::min(le,qujian[i].l);
re=std::max(qujian[i].r,re);
}
printf("%d %d\n",le,re);
}
```