有一些闭区间[ai,bi]（i=一、二、…、n），找出区间数最少的表示方案，并按递增的顺序定稿输出文件。当a≤b＜c≤d时，咱们说区间[a,b]和[c,d]为递增顺序。ios

任务：spa

你的任务是编写一个程序完成下列工做：code

• 从文件中读入这些区间；
• 算出知足上述条件的区间；
• 把结果写入文件。

输入：内存

文件的第一行是整数n，3≤n≤50000，表明区间个数，如下第i+1行1≤i≤n，有两个用空格分开的的整数ai和bi表示一个闭区间[ai,bi]（1≤ai≤bi≤1000000）。ci

输出：it

文件包括，所求的不相交闭区间，每行描述一个闭区间，按照递增顺序。每一个区间用两个以空格分开的整数表示，分别是该区间的开头和末端。io

输入样例：class

5
5 6
1 4
10 10
6 9
8 10

输出样例：stream

1 4
5 10

一遍扫描思路来自Byvoid遇到区间开始h+1，遇到结束h-1程序

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define INF 9999999
#define MAX_N 50000
#define MAX_M 1000001

int n;
struct Point
{
    int pos;
    bool start;
} pt[MAX_M];

bool cmp(const Point &a,const Point &b)
{
    if(a.pos!=b.pos)
        return a.pos<b.pos;
    else
    {
        if(a.start)
            return true;
        else
            return false;
    }
}

int main()
{
    freopen("prz.in","r",stdin);
    freopen("prz.out","w",stdout);

    int minx,maxx;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>pt[2*i].pos>>pt[2*i+1].pos;
        pt[2*i].start=true;pt[2*i+1].start=false;
    }

    sort(pt,pt+n*2,cmp);

    int n2=n*2;

    int l=0;
    int h=0;
    for(int i=0;i<n2;i++)
    {
        if(pt[i].start)
            h++;
        else
            h--;
        if(h==1 && pt[i].start)
        {
            l=pt[i].pos;
        }
        else if(h==0)
        {
            cout<<l<<" "<<pt[i].pos<<endl;
        }
    }

    return 0;
}