本题是“带容量约束的加权区间调度”问题:
既要保证所选项目在时间上两两不重叠(若一个在时间 X 结束,可接 X 开始的项目),又要满足总工作量不超过 maxEffort,并使收益最大。
做法:
i 个项目为 (s[i], e[i], w[i], v[i]),分别是开始/结束/工作量/收益。i 的“前驱” pre[i]:排序后在 i 之前、且 end <= s[i] 的最后一个项目下标(不存在则为 -1)。可用二分在结束时间数组上找到。一个项目经理需要对项目进行计划制定,现有 n 个项目,每个项目有一个开始时间 startTime[i]、结束时间 endTime[i] 以及所需投入的人力 effort[i] ,完成每个项目能获得的收益为 profit[i] 。
项目团队可以投入的最大工作量为 maxEffort ,并且在时间上重叠的项目不能同时开展。
如果一个项目在时间 X 结束,可以立刻承接在时间 X 开始的新项目。
请编写一个函数,计算在不超过可以投入最大工作量为 maxEffort 的情况下,合理安排计划获得的最大收益。