Lựa chọn hoạt động

General
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Có $N$ hoạt động, hoạt động thứ $i$ diễn ra trong khoảng thời gian $[S_i, E_i]$ ($S_i < E_i$). Một người chỉ có thể tham gia một hoạt động tại một thời điểm, và có thể tham gia hoạt động tiếp theo nếu thời gian bắt đầu của nó lớn hơn hoặc bằng thời gian kết thúc của hoạt động trước ($E_{prev} \le S_{next}$). Hãy tìm số lượng hoạt động tối đa có thể tham gia.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương $N$.\n$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $S_i, E_i$.

Dữ liệu ra

Một số nguyên duy nhất là số hoạt động tối đa.

Ví dụ
Input Output
4\n1 3\n2 5\n3 6\n5 8 2
Giới hạn

$1 \le N \le 1000$, $0 \le S_i < E_i \le 10^9$.

Draft saved