Gộp các đoạn giao nhau
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Cho $n$ đoạn đóng trên trục số $[l_i, r_i]$. Hai đoạn giao nhau (hoặc chạm nhau tại đầu mút) có thể gộp thành một đoạn duy nhất. Hãy gộp tất cả các đoạn giao nhau và in ra các đoạn kết quả theo thứ tự tăng dần.
Dữ liệu vào
Dòng đầu chứa số nguyê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
Dòng đầu in ra số nguyên $m$ là số đoạn sau khi gộp. $m$ dòng tiếp theo, mỗi dòng in ra hai số nguyên $l, r$ của từng đoạn đã gộp theo thứ tự tăng dần.
Ví dụ
Input
4
1 3
2 6
8 10
15 18
Output
3
1 6
8 10
15 18
Giới hạn
$1 \le n \le 10^5$, $-10^9 \le l_i \le r_i \le 10^9$.
Community Discussion