规划兼职工作

记住这句口诀:dp[i] = max( 不接(dp[i-1]) , 接它(dp[二分位置] + 本份收益) )。下面每填一格都在套它。

第一步,把四份工作按结束时间升序排好,得到结束 = [3,4,5,6]、开始 = [1,2,3,3]、收益 = [50,10,40,70]。排序的好处是:任何一份工作能配的「前面那批」一定是排序后连续的前缀,这样才好用二分去切。

dp 第 0 格固定是 0:还没考虑任何工作,收益自然是 0。绿色这一格是后面所有计算的地基。

现在要填 dp[1]。当前这份工作开始 1、结束 3、收益 50。它有两条路:不接它,或者接它。先看接它能配上谁。

接它的话,前面只能配「结束时间 ≤ 它的开始时间 1」的工作。在已排好的结束时间上二分,数出这样的工作有 0 份(一份都没有,它开始得太早)。这 0 份的最优组合正是 dp[0](蓝色)。

两条路算清楚:不接这份,收益沿用 dp[0] = 0;接这份,收益是它配上 dp[0] = 0,再加自己的 50,得 50。接它更高,选 50。

第 1 格结算:dp[1] = 50(绿色锁定)。后面更晚结束的工作会接着用它。

现在要填 dp[2]。当前这份工作开始 2、结束 4、收益 10。它有两条路:不接它,或者接它。先看接它能配上谁。

接它的话,前面只能配「结束时间 ≤ 它的开始时间 2」的工作。在已排好的结束时间上二分,数出这样的工作有 0 份(一份都没有,它开始得太早)。这 0 份的最优组合正是 dp[0](蓝色)。

两条路算清楚:不接这份,收益沿用 dp[1] = 50;接这份,收益是它配上 dp[0] = 0,再加自己的 10,得 10。不接更高,选 50。

第 2 格结算:dp[2] = 50(绿色锁定)。后面更晚结束的工作会接着用它。

现在要填 dp[3]。当前这份工作开始 3、结束 5、收益 40。它有两条路:不接它,或者接它。先看接它能配上谁。

接它的话,前面只能配「结束时间 ≤ 它的开始时间 3」的工作。在已排好的结束时间上二分,数出这样的工作有 1 份(结束时间 3 都 ≤ 3)。这 1 份的最优组合正是 dp[1](蓝色)。

两条路算清楚:不接这份,收益沿用 dp[2] = 50;接这份,收益是它配上 dp[1] = 50,再加自己的 40,得 90。接它更高,选 90。

第 3 格结算:dp[3] = 90(绿色锁定)。后面更晚结束的工作会接着用它。

现在要填 dp[4]。当前这份工作开始 3、结束 6、收益 70。它有两条路:不接它,或者接它。先看接它能配上谁。

接它的话,前面只能配「结束时间 ≤ 它的开始时间 3」的工作。在已排好的结束时间上二分,数出这样的工作有 1 份(结束时间 3 都 ≤ 3)。这 1 份的最优组合正是 dp[1](蓝色)。

两条路算清楚:不接这份,收益沿用 dp[3] = 90;接这份,收益是它配上 dp[1] = 50,再加自己的 70,得 120。接它更高,选 120。

第 4 格结算:dp[4] = 120(绿色锁定)。后面更晚结束的工作会接着用它。

表填满,最右一格 dp[4] = 120 就是答案。

回看具体选了谁:接第 1 份(结束 3、收益 50),它结束在 3;再接第 4 份(开始正好是 3、结束 6、收益 70),开始时间等于上一份结束时间,不冲突。两份相加 50 + 70 = 120,正是最大收益。

边界先想清:结束等于下一份开始算可接;开始时间相同的工作互斥,只能留一份。

两个追问,核心是认出「带权区间调度 = 排序 + DP + 二分」这个可推广的母题。