Chọn Công Việc
Points
12
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ công việc, mỗi công việc có thời điểm bắt đầu $s_i$ và thời điểm kết thúc $e_i$. Chọn số lượng công việc nhiều nhất sao cho không có hai công việc nào chồng chéo nhau (một công việc kết thúc tại thời điểm $t$ thì có thể bắt đầu công việc khác tại thời điểm $t$).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ $(1 \le N \le 10^5)$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $s_i$ và $e_i$ $(0 \le s_i < e_i \le 10^9)$.
Dữ liệu ra
- In ra số lượng công việc nhiều nhất có thể chọn.
Ví dụ
| Input | Output |
|---|---|
| 3 1 3 2 5 3 6 |
2 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le s_i < e_i \le 10^9$
Community Discussion