Chụp Ảnh Khoảng Thời Gian
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Có $N$ vị khách tham dự triển lãm, vị khách thứ $i$ có mặt liên tục từ thời điểm $L_i$ đến $R_i$. Nhiếp ảnh gia muốn chọn ít thời điểm chụp ảnh nhất sao cho mỗi vị khách đều xuất hiện trong ít nhất một bức ảnh (tức là với mỗi $i$, có ít nhất một thời điểm chụp $t$ thỏa mãn $L_i \le t \le R_i$).
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$.
- $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $L_i, R_i$.
Dữ liệu ra
Một số nguyên duy nhất là số thời điểm chụp ảnh ít nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 2 5 4 7 8 10 |
3 |
Giới hạn
- $1 \le N \le 10^5$.
- $1 \le L_i \le R_i \le 10^9$.
Community Discussion