題目描述

給定一個數軸上的?𝑛n?個閉區間，第?𝑖i?個閉區間的兩端點為[𝑎𝑖,𝑏𝑖][ai?,bi?]，它們的并集可以表示為若干不相交的閉區間，請按照左端點從小到大的順序輸出這些區間的并集。

輸入格式

• 第一行：單個整數?𝑛n；
• 第二行到第?𝑛+1n+1?行：每行兩個整數?𝑎𝑖ai??與?𝑏𝑖bi??表示一個閉區間?[𝑎𝑖,𝑏𝑖][ai?,bi?]。

輸出格式

若干行：表示輸入區間的并集。每行兩個整數，表示一個閉區間的兩個端點，這些閉區間應該按照起點從小到大排序。

數據范圍

• 對于?50%50%?的數據，1≤𝑛≤1041≤n≤104，0≤𝑎𝑖≤𝑏𝑖≤1040≤ai?≤bi?≤104
• 對于?100%100%?的數據，1≤𝑛≤1051≤n≤105，0≤𝑎𝑖≤𝑏𝑖≤1090≤ai?≤bi?≤109

樣例數據

輸入:

3
10 12
1 3
2 5

輸出:

1 5
10 12

詳見代碼:

#include<bits/stdc++.h>
using namespace std;
struct st 
{int a;int b;
};
struct st s[100005];
bool cmp(struct st x, struct st y) 
{if (x.a == y.a) return x.b < y.b;return x.a < y.a;
}
int main() 
{int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> s[i].a >> s[i].b;}sort(s + 1, s + n + 1, cmp);int l, r;l = s[1].a;r = s[1].b;for (int i = 2; i <= n; i++) {if (s[i].a <= r) {r = max(r,s[i].b);} else {cout << l << " " << r << endl;l = s[i].a;r = s[i].b;}}cout << l << " " << r << endl;return 0;
}