Chọn hoạt động không giao nhau
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Có $N$ hoạt động, hoạt động thứ $i$ bắt đầu tại thời điểm $L_i$ và kết thúc tại $R_i$ ($L_i < R_i$). Hai hoạt động được coi là không giao nhau nếu thời điểm kết thúc của hoạt động trước nhỏ hơn hoặc bằng thời điểm bắt đầu của hoạt động sau. Hãy tìm số lượng hoạt động tối đa có thể chọn.
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 $L_i$ và $R_i$.
Dữ liệu ra
In ra số lượng hoạt động tối đa có thể chọn.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 2 5 3 6 5 8 |
2 |
Giới hạn
- $1 \le N \le 10^5$.
- $0 \le L_i < R_i \le 10^9$.
Community Discussion