Hợp Nhất Các Khoảng Giao Nhau

Buổi 10 — STL Algorithms sorting
Points
30
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$ có dạng $[L_i, R_i]$. Hai đoạn thẳng giao nhau (kể cả chạm nhau tại một điểm đầu mút) có thể hợp nhất thành một đoạn duy nhất.

Hãy hợp nhất tất cả các đoạn giao nhau và in ra danh sách 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$ ($1 \le N \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i, R_i$ ($-10^9 \le L_i \le R_i \le 10^9$).
Dữ liệu ra
  • Dòng đầu tiên in ra số lượng đoạn sau khi hợp nhất $K$.
  • $K$ dòng tiếp theo, mỗi dòng in ra hai số nguyên $L, R$ của đoạn tương ứng.
Ví dụ
Input Output
4
1 3
2 6
8 10
15 18
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$
Draft saved