Gộp các đoạn thẳng chồng lấn
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề 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$.
Community Discussion