Tại một trung tâm hội nghị có một hội trường lớn, rất đẹp nên nhận được $n$ đơn đặt hàng của $n$ công ty sự kiện. Công ty thứ $i$ muốn sử dụng hội trường này trong khoảng thời gian từ $a_i$ đến $b_i$ và trả tiền thuê là $c_i$.

Yêu cầu: Hãy bố trí lịch thuê hội trường để tổng số tiền thu được là lớn nhất mà thời gian sử dụng hội trường của hai công ty bất kỳ đều không trùng nhau.

5
1 2 100
5 6 300
3 4 200
7 8 400
8 10 200

1000