Intervals

Interview

Time limit1sMemory limit128 MB

Summary

Given n closed intervals, merge all overlapping or touching ones and print the resulting disjoint intervals in ascending order.

Level: Easy3 of 10
Topics: Sorting, Intervals, Greedy, Array
Solved: No attempts yet

Problem

You are given $n$ closed intervals $[a_i, b_i]$ , where $i = 1, 2, \dots, n$ . The union of these intervals can be represented as a sum of pairwise non-intersecting closed intervals. Find such a representation that uses the minimal number of intervals, and print those intervals in ascending order. Two intervals $[a, b]$ and $[c, d]$ are in ascending order if and only if $a \le b < c \le d$ .

Write a program that:

reads the description of the intervals from standard input,
computes the pairwise non-intersecting intervals satisfying the conditions above,
writes the computed intervals in ascending order to standard output.

Input

The first line contains one integer $n$ , the number of intervals ( $3 \le n \le 50000$ ). Each of the next $n$ lines contains a description of interval $[a_i, b_i]$ as two integers $a_i$ and $b_i$ separated by a single space, the beginning and the end of the interval respectively, with $1 \le a_i \le b_i \le 1000000$ .

Output

Print the descriptions of all computed pairwise non-intersecting intervals. Each line contains the description of one interval: two integers separated by a single space, the beginning and the end of the interval respectively. The intervals must be printed in ascending order.

Examples2

Example 1
Input
```
5
5 6
1 4
10 10
6 9
8 10
```
Expected output
```
1 4
5 10
```
Example 2
Input
```
3
7 8
1 2
4 5
```
Expected output
```
1 2
4 5
7 8
```