题目描述

给出 nn 个区间，请合并所有重叠的区间，并把合并后的区间按升序输出。

注意：当且仅当 a \le b \lt c \le da≤b<c≤d 时，区间 [a,ba,b] 、[c,dc,d] 才是升序

输入格式

第一行只有一个数 nn ( 3 \le n \le 500003≤n≤50000 )，代表区间数。

接下来 nn 行有两个数 a_i,b_iai​,bi​，之间用一个空格隔开，分别表示区间 [a_iai​,b_ibi​]的起始和结束 ( 1 \le a_i \le b_i \le 10000001≤ai​≤bi​≤1000000)

输出格式

计算出的所有区间，每行写一个区间，每行只有两个数，分别是区间起始和结束，之间用一个空格分开。记住必须是按升序输出。

样例

输入数据 1

5
5 6
1 4
10 10
6 9
8 10

Copy

输出数据 1

1 4
5 10

#include<bits/stdc++.h>
using namespace std;
struct z{
    int l,r;
}a[50005];
bool cmp(z i, z j){
    return i.l<j.l||(i.l==j.l&&i.r<j.r);
}
int n,r1,l1;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
    }
    sort(a+1,a+1+n,cmp);
    a[++n].l = 2000000;
    l1=a[1].l;
    r1=a[1].r;
    for(int i=2;i<=n;i++){
        if(a[i].l<=r1)
        r1 = max(a[i].r,r1);
        else{
        printf("%d %d\n",l1,r1);
        l1 = a[i].l;
        r1 = a[i].r;
        }
    }
    return 0;
}