规划兼职工作 图解题解

规划兼职工作到底在挑哪几份

给三个等长数组 startTime、endTime、profit，第 i 份工作占区间 [开始, 结束)（右端不含：上一份结束正好等于下一份开始，不算重叠）、做完拿 profit[i]。挑若干份、时间互不重叠，让收益之和最大。题面 start=[1,2,3,3]、end=[3,4,5,6]、profit=[50,10,40,70]，答案 120。

为什么挨个试选或不选会爆

每份工作都有「选」「不选」两条岔路，n 份就有 2ⁿ 种组合，逐一验重叠求和，n 一大数不完，且组合前半截大量重合被反复重算。把「前面若干份的最优收益」记下来复用就省了——这就是动态规划（DP，把前若干份工作的最大报酬记表、后面直接取）。

按结束时间排序，dp[i] 到底存什么

先把工作按结束时间从小到大排好，本例得结束 = [3,4,5,6]、开始 = [1,2,3,3]、收益 = [50,10,40,70]。排好后，任一份工作「能接在前面的那批」必是连续的一段前缀（前缀=最靠前的一段），才好用二分（在有序数据里对半砍、快速定位的查法）切出来。据此定义 dp[i]：前 i 份、不重叠时能拿的最大收益。dp[0] = 0：没考虑任何工作。

接一份工作，前驱该从哪一格接

填 dp[i] 时，第 i 份只有两条路。不接它，收益沿用 dp[i-1]。接它，就先找前面「结束时间 ≤ 它的开始时间」的工作，份数记作 j，用二分找结束时间里「第一个大于当前开始时间的位置」，那个下标就是 j。

前 j 份的最优收益存在 dp[j] 里，接上加本份 profit 就是「接这份」的收益。两条取大，转移（由已算好的格子推出当前格的式子）即 dp[i] = max(dp[i-1], dp[j] + profit)。

拿题面四份工作把表填出来

接上一节排好的顺序填表，dp[0] = 0。前两份开始 1、2。第 1 份最靠前、没有前驱；第 2 份开始 2，排在它前面的只有第 1 份、结束在 3，3 > 2 接不上，两份都只能单干：dp[1] = 50；第 2 份自身 10 不如沿用，dp[2] = 50。第 3 份开始 3、收益 40，结束 ≤ 3 有 1 份，接 dp[1] 得 90 胜过 50，dp[3] = 90。第 4 份开始 3、收益 70，结束 ≤ 3 有 1 份，接 dp[1] 得 120 胜过 90，dp[4] = 120。

二分边界写成 <，正好接得上的那份为什么会丢

把二分等号写丢——用「结束时间 < 开始时间」找前驱，第 3 份卡在 3 = 3 的工作被排除，dp[4] 接不到 dp[1]，120 缩水成 90，题面明明写着结束等于开始算可接，代码就得用 ≤。另一处是排序键：必按结束时间排，可接工作才凑成能二分的前缀，错按开始或收益排就失效。

排序花 O(n log n)（大 O 记号描述数据规模变大时操作数怎么涨），之后填 n 格、每格一次二分是 O(log n)，合起来仍是 O(n log n)，对 n 到 5 万完全够用；dp 与结束时间数组都是 O(n) 空间。

Python

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]

C++

#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();
    }
};

Java

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;
    }
}