规划兼职工作 图解题解

这道题到底在问什么

输入

start=[1,2,3,3], end=[3,4,5,6], profit=[50,10,40,70]

输出

120　(选第 1 份收益 50 + 第 4 份收益 70)

最优解：一步一步想明白

1. 3记住这句口诀:dp[i] = max( 不接(dp[i-1]) , 接它(dp[二分位置] + 本份收益) )。下面每填一格都在套它。
2. 4第一步,把四份工作按结束时间升序排好,得到结束 = [3,4,5,6]、开始 = [1,2,3,3]、收益 = [50,10,40,70]。排序的好处是:任何一份工作能配的「前面那批」一定是排序后连续的前缀,这样才好用二分去切。
3. 5dp 第 0 格固定是 0:还没考虑任何工作,收益自然是 0。绿色这一格是后面所有计算的地基。
4. 6现在要填 dp[1]。当前这份工作开始 1、结束 3、收益 50。它有两条路:不接它,或者接它。先看接它能配上谁。
5. 7接它的话,前面只能配「结束时间 ≤ 它的开始时间 1」的工作。在已排好的结束时间上二分,数出这样的工作有 0 份(一份都没有,它开始得太早)。这 0 份的最优组合正是 dp[0](蓝色)。
6. 8两条路算清楚:不接这份,收益沿用 dp[0] = 0;接这份,收益是它配上 dp[0] = 0,再加自己的 50,得 50。接它更高,选 50。
7. 9第 1 格结算:dp[1] = 50(绿色锁定)。后面更晚结束的工作会接着用它。
8. 10现在要填 dp[2]。当前这份工作开始 2、结束 4、收益 10。它有两条路:不接它,或者接它。先看接它能配上谁。
9. 11接它的话,前面只能配「结束时间 ≤ 它的开始时间 2」的工作。在已排好的结束时间上二分,数出这样的工作有 0 份(一份都没有,它开始得太早)。这 0 份的最优组合正是 dp[0](蓝色)。
10. 12两条路算清楚:不接这份,收益沿用 dp[1] = 50;接这份,收益是它配上 dp[0] = 0,再加自己的 10,得 10。不接更高,选 50。
11. 13第 2 格结算:dp[2] = 50(绿色锁定)。后面更晚结束的工作会接着用它。
12. 14现在要填 dp[3]。当前这份工作开始 3、结束 5、收益 40。它有两条路:不接它,或者接它。先看接它能配上谁。
13. 15接它的话,前面只能配「结束时间 ≤ 它的开始时间 3」的工作。在已排好的结束时间上二分,数出这样的工作有 1 份(结束时间 3 都 ≤ 3)。这 1 份的最优组合正是 dp[1](蓝色)。
14. 16两条路算清楚:不接这份,收益沿用 dp[2] = 50;接这份,收益是它配上 dp[1] = 50,再加自己的 40,得 90。接它更高,选 90。
15. 17第 3 格结算:dp[3] = 90(绿色锁定)。后面更晚结束的工作会接着用它。
16. 18现在要填 dp[4]。当前这份工作开始 3、结束 6、收益 70。它有两条路:不接它,或者接它。先看接它能配上谁。
17. 19接它的话,前面只能配「结束时间 ≤ 它的开始时间 3」的工作。在已排好的结束时间上二分,数出这样的工作有 1 份(结束时间 3 都 ≤ 3)。这 1 份的最优组合正是 dp[1](蓝色)。
18. 20两条路算清楚:不接这份,收益沿用 dp[3] = 90;接这份,收益是它配上 dp[1] = 50,再加自己的 70,得 120。接它更高,选 120。
19. 21第 4 格结算:dp[4] = 120(绿色锁定)。后面更晚结束的工作会接着用它。
20. 22表填满,最右一格 dp[4] = 120 就是答案。
21. 23回看具体选了谁:接第 1 份(结束 3、收益 50),它结束在 3;再接第 4 份(开始正好是 3、结束 6、收益 70),开始时间等于上一份结束时间,不冲突。两份相加 50 + 70 = 120,正是最大收益。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from bisect import bisect_right
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))
        ends = [e for e, _, _ in jobs]
        dp = [0] * (len(jobs) + 1)
        for i, (e, s, p) in enumerate(jobs, 1):
            j = bisect_right(ends, s, 0, i - 1)
            dp[i] = max(dp[i - 1], dp[j] + p)
        return dp[-1]

#include <algorithm>
#include <tuple>
#include <vector>
using namespace std;
class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<tuple<int,int,int>> jobs;
        for (int i = 0; i < (int)startTime.size(); ++i) jobs.push_back({endTime[i], startTime[i], profit[i]});
        sort(jobs.begin(), jobs.end());
        vector<int> ends, dp(jobs.size() + 1);
        for (auto [e, s, p] : jobs) ends.push_back(e);
        for (int i = 1; i <= (int)jobs.size(); ++i) {
            auto [e, s, p] = jobs[i - 1];
            int j = upper_bound(ends.begin(), ends.begin() + i - 1, s) - ends.begin();
            dp[i] = max(dp[i - 1], dp[j] + p);
        }
        return dp.back();
    }
};

import java.util.*;
class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) { jobs[i][0] = endTime[i]; jobs[i][1] = startTime[i]; jobs[i][2] = profit[i]; }
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
        int[] ends = new int[n], dp = new int[n + 1];
        for (int i = 0; i < n; i++) ends[i] = jobs[i][0];
        for (int i = 1; i <= n; i++) {
            int s = jobs[i - 1][1], p = jobs[i - 1][2];
            int j = upperBound(ends, i - 1, s);
            dp[i] = Math.max(dp[i - 1], dp[j] + p);
        }
        return dp[n];
    }
    private int upperBound(int[] a, int hi, int target) {
        int l = 0, r = hi;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a[m] <= target) l = m + 1; else r = m;
        }
        return l;
    }
}

复杂度

面试官可能追问