题解 P2434 【[SDOI2005]区间】

**题目描述** 给定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); } ```