Gộp các đoạn thẳng chồng lấn

General
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho $N$ đoạn thẳng trên trục số, đoạn thứ $i$ là $[L_i, R_i]$. Hai đoạn giao nhau (kể cả chạm tại một điểm đầu mút) có thể gộp thành một đoạn bao trùm cả hai. Hãy gộp tất cả các đoạn giao nhau và in ra các đoạn rời nhau thu được theo thứ tự tăng dần.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương $N$.\n$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i, R_i$ ($L_i \le R_i$).

Dữ liệu ra

Gồm $K$ dòng ($K$ là số đoạn sau khi gộp), mỗi dòng in hai số nguyên $L\ R$ tăng dần.

Ví dụ
Input Output
4\n1 3\n2 6\n8 10\n15 18 1 6\n8 10\n15 18
Giới hạn

$1 \le N \le 1000$, $-10^9 \le L_i \le R_i \le 10^9$.

Draft saved