解题思路

• 本题是“带容量约束的加权区间调度”问题： 既要保证所选项目在时间上两两不重叠（若一个在时间 X 结束，可接 X 开始的项目），又要满足总工作量不超过 maxEffort，并使收益最大。

• 做法：

  1. 将项目按结束时间从小到大排序，记排序后第 i 个项目为 (s[i], e[i], w[i], v[i])，分别是开始/结束/工作量/收益。
  2. 预处理每个项目 i 的“前驱” pre[i]：排序后在 i 之前、且 end <= s[i] 的最后一个项目下标（不存在则为 -1）。可用二分在结束时间数组上找到。
  3. 二维动态规划（DP）：

题目内容

一个项目经理需要对项目进行计划制定，现有 $n$ 个项目，每个项目有一个开始时间 $startTime[i]$、结束时间 $endTime[i]$ 以及所需投入的人力 $effort[i]$ ，完成每个项目能获得的收益为 $profit[i]$ 。

项目团队可以投入的最大工作量为 $maxEffort$ ，并且在时间上重叠的项目不能同时开展。

如果一个项目在时间 $X$ 结束，可以立刻承接在时间 $X$ 开始的新项目。

请编写一个函数，计算在不超过可以投入最大工作量为 $maxEffort$ 的情况下，合理安排计划获得的最大收益。

输入描述

函数包含 $5$ 个参数，前四个数组参数，长度相同且 $≤ 2000$，数值均 $≤10^9$ ，$5$ 个参数分 $5$ 行输入，数组数据以 "$,$" 分割，示例如下:

1、开始时间数组 $startTime,0≤$ 数组长度及数据 $≤2000$ ，示例: $1$ $5$ $9$ ;

2、结束时间数组 $endTime，0≤$ 数组长度及数据 $≤2000$ ，示例: $3$ $7$ $11$ ;

3、所需投入的工作量 $effort，0≤$ 数组长度及数据 $≤2000$ ，示例:$20$ $30$ $10$ ;

4、以及获得收益数组 $profit$ ，$0≤$ 数组长度及数据 $≤2000$ ，示例:$20$ $80$ $30$ ;

5、可以投入最大工作量 $maxEffort，0 ≤ maxEffort ≤1000$ ，示例:$40$

输入完整示例如下:

$1,5,9$

$3,7,11$

$20,30,10$

$20,80,30$

$40$

输出描述

在不超过每日工作量上限的情况下，安排合理计划获得最大收益

样例1

输入

2 4 7
6 8 11
20 20 20
30 90 30
40

输出

90

说明

选择第二个项目，由于时间与其他项目时间重叠

无法选取其他项目，总精力为 $20<=40$ ,总收益为 $90$

样例2

输入

1 5 9
3 7 11
20 30 10
20 80 30
40

输出

110

说明 选择第二个和第三个项目，总精力为 $30+10=40<=40$ ,总收益为 $80+30=110$