GS的一道区间调度问题 租车给那些人？

A car has to be given on rent. Different people come and ask for it for interval [s,e] and offer some price p. To whom shall the car be given in order to earn maximum.

这里To whom 应该是指复数。对于这组数据应该最高出租69。

1.       |--------------| ￥60
   
2.                 |------------------| ￥32
   
3.         |----------| ￥55
   
4.             |-------------------| ￥6
   
5.                           |----| ￥9
   
6.           |----| ￥17
   

复制代码

很古老的dp题了
按截止时间排序所有任务
dp[i] 表示截止至第 i 时刻能赚到的最大价值
枚举时间，
1 - 若当前不是某个任务的截止时间，则 dp[i]=dp[i-1]
2 - 若当前是某个任务的截止时间：
那么面临的选择就有，选择 or 不选择这个任务：
选择的话： dp[s-1]+ 这个任务的收益  （也就是选择这个任务，那么最大收益就是在开始任务前的最大收益加上这个任务的收益）
不选择的话： dp[i]
取最大值即可。