Chụp Ảnh Khoảng Thời Gian

General
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề 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$.
Draft saved