Chọn tối đa khóa học
Points
42
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Có $N$ khóa học trực tuyến khác nhau, khóa học thứ $i$ kéo dài trong $t_i$ ngày và phải được hoàn thành không muộn hơn ngày thứ $d_i$. Bạn bắt đầu học từ ngày thứ $1$ và tại mỗi thời điểm chỉ có thể học tối đa một khóa (không thể học song song). Hãy tìm số lượng khóa học tối đa bạn có thể hoàn thành.
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 $t_i$ và $d_i$.
Dữ liệu ra
Một số nguyên duy nhất là số lượng khóa học tối đa có thể hoàn thành.
Ví dụ
| Input | Output |
|---|---|
| 4\n100 200\n200 1300\n1000 1250\n2000 3200 | 3 |
| 2\n3 2\n4 3 | 0 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le t_i, d_i \le 10^9$
Community Discussion