Chọn Công Việc

Buổi 12 — Greedy Algorithm Buổi 16 — Contest Chặng 2 sorting
Points
12
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved