Tham dự tối đa sự kiện

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