Giúp ý tưởng bài tập

[sontt (nguyễn thái sơn)]

Minh có một chiếc xe taxi 4 chỗ. Trong dịp tết nguyên đán lượng khách hành rất đông vì thế ai muốn được phục vụ thì phải gọi trước môt ngày để minh sắp xếp. Trong số N khách hàng cửa Minh, khách hàng thứ i muốn thuê xe trong khoảng thời gian từ ai đến bi và trả một khoản phí là ci(ai,bi là các số tự nhiên <25, 0<ci<100). Bạn hãy giúp Minh bố trí lịch phục vụ khách hàng để tổng số tiền thu được là lớn nhất mà thời gian 2 khách hàng bất kì được phục vụ không giao nhau.

Dữ liệu vào tệp TAXI.INP gồm 4 dòng.

• Dòng 1 chứa 1 số tự nhiên N(0<N<100).
• Dòng 2 là khoảng thời gian bắt đầu của từng khách hàng thứ i đặt.
• Dòng 3 là khoảng thời gian kết thức khách hàng thứ i đặt.
• Dòng 4 là số tiền khách hàng thứ i trả nếu được phục vụ.

Dữ liệu ra: Đưa ra tệp TAXI.OUT là một số duy nhất thể hiện số tiền thu được

Ví dụ:
TAXI.INP
5
2 4 6 4 3
3 5 9 6 8
6 4 7 9
TAXI.OUT
22

ý tưởng của mk
sắp xếp phần input như sau( bc này mk ko bt lm thế nào)
2 3 4 4 6
3 8 5 6 9
6 4 9 7
sau đó quy về bài toán dãy con tăng dần có tổng lớn nhất

[nguyenchiemminhvu (NCMV)]

Bài tập này có dạng gần giống với bài toán Activity Selection: https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/

Nhưng với bài toán Activity Selection, giá trị max người ta muốn tìm là số lượng công việc làm được, chứ không phải tìm giá trị (có thể là số tiền công) lớn nhất mà người đó làm ra được.

Trong trường hợp này, nó giống với bài toán Weighted Activity Selection, giải pháp tối ưu cho bài toán này chắc phải dùng Dynamic Programming. Bạn có thể search với từ khoá: “Weighted Activity Selection Problem Dynamic Programming” và tìm hiểu thêm.