问题解构LeetCode 1235 “规划兼职工作”这是一个动态规划结合二分查找的经典问题属于“区间调度”问题的变种。题目要求在一系列兼职工作中进行选择以最大化总收益。核心要素每份工作由[startTime, endTime, profit]表示。你不能同时参与两份工作即选择的工作时间区间不能重叠。目标是选择若干份互不重叠的工作使得这些工作的总收益最大。解题思路解决此问题的关键在于排序和状态定义。一个高效的思路是排序将所有工作按照结束时间endTime从小到大排序。这有助于我们快速找到“在前一份工作结束后可以开始的下一份工作”。动态规划定义定义dp[i]表示考虑前i份工作时能获得的最大收益。对于第i份工作排序后的我们有两种选择不选它那么最大收益就是dp[i-1]。选择它那么我们必须找到在它开始之前刚刚结束的那份工作j。最大收益就是profit[i] dp[j]。因此状态转移方程为dp[i] max(dp[i-1], profit[i] dp[j])。寻找工作j由于我们已经按结束时间排序可以使用二分查找在0到i-1的范围内快速找到最后一个结束时间 startTime[i]的工作索引j。这是优化时间复杂度的关键。C 代码实现完整注释版class Solution { public: int jobScheduling(vectorint startTime, vectorint endTime, vectorint profit) { int n startTime.size(); // 1. 将工作打包并按照结束时间排序 vectorvectorint jobs(n, vectorint(3)); for (int i 0; i n; i) { jobs[i] {startTime[i], endTime[i], profit[i]}; } // 按结束时间升序排序 sort(jobs.begin(), jobs.end(), [](const vectorint a, const vectorint b) { return a[1] b[1]; }); // 2. 动态规划数组dp[i] 表示考虑前 i 份工作排序后的最大收益 vectorint dp(n 1, 0); // 为了方便处理让下标从1开始dp[0]0 表示没有工作时的收益为0 for (int i 1; i n; i) { int currStart jobs[i-1][0]; int currProfit jobs[i-1][2]; // 3. 二分查找找到最后一个结束时间 当前工作开始时间的工作索引 j // jobs[0...j-1] 的结束时间都 currStart int left 0, right i - 1; // 在 jobs[0...i-2] 中查找 while (left right) { int mid left (right - left) / 2; if (jobs[mid][1] currStart) { left mid 1; // 继续向右找更晚结束的 } else { right mid - 1; } } // 循环结束时right 指向最后一个满足条件的索引 int j right 1; // 因为dp下标从1开始所以需要1。dp[j] 对应 jobs[0...right] 的最大收益 // 4. 状态转移选择当前工作 或 不选当前工作 dp[i] max(dp[i-1], currProfit dp[j]); } // 5. 最终结果 return dp[n]; } };算法步骤详解数据重组与排序将三个独立的数组合并成一个jobs列表每个元素是[start, end, profit]。按照end结束时间进行升序排序。排序是后续进行二分查找和动态规划的基础。动态规划初始化创建dp数组长度为n1。dp[i]表示处理完前i份工作排序后能获得的最大收益。dp[0] 0作为边界条件。核心循环状态计算遍历每一份工作i从1到n选项一不选当前工作。收益直接继承dp[i-1]。选项二选择当前工作。收益为当前工作的利润在它开始前能完成的所有工作的最大收益。为了计算选项二需要通过二分查找找到“在它开始前能完成的所有工作中最后结束的那一个”的索引j。dp[j]就是这部分的最大收益。二分查找细节在已排序的jobs[0...i-2]中查找最后一个满足jobs[mid][1] currStart的位置。使用标准的二分查找模板最终right指向目标位置。因为dp索引从1开始所以j right 1。获取结果最终dp[n]就是考虑所有n份工作后能获得的最大收益。举例说明假设输入为startTime [1,2,3,4,6] endTime [3,5,10,6,9] profit [20,20,100,70,60]处理过程排序后的工作列表jobs为按endTime排序[[1,3,20], [2,5,20], [4,6,70], [6,9,60], [3,10,100]]动态规划计算i1(工作[1,3,20])前面没有工作dp[1] max(0, 200) 20i2(工作[2,5,20])查找end2的工作找到工作1。dp[2] max(20, 2020) 40i3(工作[4,6,70])查找end4的工作找到工作2。dp[3] max(40, 7040) 110i4(工作[6,9,60])查找end6的工作找到工作3。dp[4] max(110, 60110) 170i5(工作[3,10,100])查找end3的工作找到工作1。dp[5] max(170, 10020) 170最终结果dp[5] 170。最优选择选择工作[1,3,20]、[4,6,70]和[6,9,60]总收益为207060150等等这里似乎计算有误。让我们仔细核对一下动态规划的过程。实际上根据我们的状态转移对于工作[6,9,60]当i4时我们找到end6的工作是[4,6,70]即j3所以dp[4] max(dp[3], 60 dp[3]) max(110, 60110)170。这意味着我们选择了[6,9,60]和它之前最优的组合即[1,3,20]和[4,6,70]但[4,6,70]和[6,9,60]时间上并不重叠一个在6结束一个在6开始这是允许的。所以总收益是207060150但dp[4]170这里出现了矛盾。矛盾排查问题出在二分查找的索引转换上。在代码中jobs索引从0开始dp索引从1开始。当我们找到right后j right 1。dp[j]对应的是jobs[0...right]的最大收益。对于[6,9,60](i4,jobs[3])currStart6。二分查找在jobs[0..2]中找end6的最后一个工作是[4,6,70](jobs[2])所以right2j3。dp[3]是考虑jobs[0], jobs[1], jobs[2]的最大收益即[1,3,20],[2,5,20],[4,6,70]这三份工作的最优解。它们互不重叠吗[1,3,20]和[4,6,70]不重叠可以同时选收益207090。[2,5,20]与[1,3,20]重叠与[4,6,70]不重叠但[1,3,20][4,6,70]90大于[2,5,20][4,6,70]90。所以dp[3]应该是90。因此dp[4] max(dp[3]90, 60 dp[j]6090150) 150。这样就和手动计算一致了。所以修正后的最优选择确实是[1,3,20],[4,6,70],[6,9,60]总收益150。dp[5]最终也是150。复杂度分析时间复杂度O(n log n)。排序需要O(n log n)。动态规划循环n次每次循环中进行一次二分查找O(log n)。因此总时间为O(n log n)。空间复杂度O(n)。用于存储jobs组合数组和dp数组。关键点总结排序是突破口按结束时间排序后保证了在考虑第i份工作时所有可能在其之前结束的工作都已经被考虑过并且可以通过二分查找快速定位。状态定义dp[i]表示考虑前i份工作而非一定选择第i份工作。这涵盖了所有可能性。二分查找优化这是将朴素动态规划O(n²)优化到O(n log n)的关键。它避免了为每个i都向前线性扫描寻找不重叠的工作。索引映射注意jobs索引从0开始与dp索引从1开始之间的转换这是代码实现中的一个常见技巧能让边界条件处理更清晰。
