Tham dự tối đa sự kiện
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Có $N$ sự kiện, sự kiện thứ $i$ diễn ra từ ngày $S_i$ đến ngày $E_i$ (tính cả hai ngày đầu cuối). Bạn có thể tham dự một sự kiện nếu bạn chọn một ngày $d$ bất kỳ sao cho $S_i \le d \le E_i$. Tuy nhiên, mỗi ngày bạn chỉ được tham dự tối đa $1$ sự kiện. Hãy tìm số lượng sự kiện tối đa bạn có thể tham dự.
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 dương $S_i$ và $E_i$.
Dữ liệu ra
In ra số lượng sự kiện tối đa có thể tham dự.
Ví dụ
| Input | Output |
|---|---|
| 4 1 2 2 3 3 4 1 2 |
4 |
| 3 1 1 1 1 1 1 |
1 |
Giới hạn
- $1 \le N \le 10^5$.
- $1 \le S_i \le E_i \le 10^5$.
Community Discussion