总时间限制: 

1000ms

内存限制: 

65536kB

描述

给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1;2] 和 [2;3] 可以合并为 [1;3]，[1;3] 和 [2;4] 可以合并为 [1;4]，但是[1;2] 和 [3;4] 不可以合并。

我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。

输入

第一行为一个整数n，3 ≤ n ≤ 50000。表示输入区间的数量。

之后n行，在第i行上（1 ≤ i ≤ n），为两个整数 ai 和 bi ，整数之间用一个空格分隔，表示区间 [ai; bi]（其中 1 ≤ ai ≤ bi ≤ 10000）。

输出

输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。

样例输入

55 61 510 106 98 10

样例输出

1 10 思路： 刚开始暴力，不行，有多种情况，单边排序还需要双重循环来照顾，果然超时。 然后想到上个火车进站的区间覆盖思路去做，合并成一张表排序，然后找规律 上次那个火车进站是求一个Max，即为相交的最大区间数。加上模拟，进一个出一个。这个合并情况不一样。 只需要判断当sum=0的情况下右边已经不存在l了即可。即遇l加1，遇r减1，不能存在独立的区间 eg： 　　3 　　1 2 　　1 3  　 4 5 合并排序之后： 1 1 2 3 4 5 l l r r l r 最后一个l出现是sum=0,这种情况就不行的 而 3 1 9 3 4 5 6 合并后 1 3 4 5 6 9 l l r l  r r 这种明显就可以。

#include 
       
        using namespace std;const int maxn = 50000*2+10;struct Node{    int x;    char s;} node[maxn];int cmp(Node a,Node b){    if(a.x != b.x)    {        return a.x < b.x;    }    else    {        return a.s < b.s;    }}int main(){//    freopen("in.txt","r",stdin);    int n;    while(~scanf("%d",&n)){    for(int i = 0; i < n*2; i++)    {        scanf("%d",&node[i].x);        if((i+1)%2==1)            node[i].s = 'l';        else        {            node[i].s = 'r';        }    }    sort(node,node+n*2,cmp);    int flag = 0;    int sum = 1;//默认跳过第一个左区间即可    for(int i = 1; i < n*2; i++)    {        if(node[i].s == 'l')        {            if(sum == 0) {                flag = 1;            }            sum++;                    }        else            sum--;    }    if(flag == 1)    {        puts("no");    }    else    {        printf("%d %d\n",node[0].x,node[n*2-1].x);    }    }    return 0;}