Một nhân viên tư vấn có lời mời làm việc, công việc thứ bắt đầu tại thời điểm và kết thúc tại thời điểm . Vì không thể làm hai việc cùng một lúc, nhân viên này muốn nhận lời mời của nhiều công việc nhất có thể sao cho thời gian làm việc của chúng không giao nhau. Một công việc được xem là không giao với công việc khác nếu khoảng thời gian làm việc của chúng không có điểm chung (có thể tiếp xúc ở đầu mút).
Hãy giúp nhân viên này tìm ra số lượng công việc tối đa có thể nhận.
Dữ liệu:
Dòng đầu tiên chứa số nguyên .
dòng tiếp theo, mỗi dòng chứa hai số nguyên là thời gian bắt đầu và kết thúc của công việc thứ .
Kết quả: Một số nguyên duy nhất là số lượng công việc tối đa có thể chọn.
Ví dụ:
Dữ liệu:
6
1 3
2 5
4 7
6 9
8 10
5 8
Kết quả:
3
Giải thích: Có thể chọn các công việc (1, 3), (4, 7), và (8, 10).
