Chọn hoạt động

Buổi 12 — Greedy Algorithm greedy sorting
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$
Draft saved