Chọn hoạt động
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Có $N$ hoạt động được đề xuất sử dụng chung một hội trường. Hoạt động thứ $i$ bắt đầu vào thời điểm $l_i$ và kết thúc vào thời điểm $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 này nhỏ hơn hoặc bằng thời điểm bắt đầu của hoạt động kia. Hãy chọn ra nhiều hoạt động nhất sao cho không có hai hoạt động nào giao nhau.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i, r_i$.
Dữ liệu ra
Một số nguyên duy nhất là số lượng hoạt động tối đa có thể chọn.
Ví dụ
| Input | Output |
|---|---|
| 3\n1 3\n2 4\n3 5 | 2 |
| 4\n1 2\n2 3\n3 4\n1 4 | 3 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le l_i < r_i \le 10^9$
Community Discussion