Có dự án có sẵn cho bạn. Đối với mỗi dự án, bạn biết ngày bắt đầu, ngày kết thúc và tiền thưởng nhận được khi hoàn thành. Bạn chỉ có thể làm việc trên một dự án tại một thời điểm. Hai dự án và được coi là không giao nhau nếu hoặc .
Yêu cầu: Hãy chọn một tập hợp con các dự án không giao nhau sao cho tổng tiền thưởng bạn nhận được là lớn nhất.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên : số lượng dự án.
dòng tiếp theo, mỗi dòng chứa ba số nguyên : ngày bắt đầu, ngày kết thúc và tiền thưởng của dự án thứ .
Kết quả: In ra tổng tiền thưởng tối đa có thể đạt được.
Ví dụ:
Dữ liệu:
4
2 4 4
3 6 6
6 8 2
5 7 3
Kết quả:
7
Giải thích: Bạn có thể chọn dự án đầu tiên ( thưởng 4) và dự án thứ tư ( thưởng 3), tổng thưởng là 7.
Đây là lựa chọn tối ưu.
