---

1235. 规划兼职工作

• 标签：数组、二分查找、动态规划、排序
• 难度：困难

题目链接

• 1235. 规划兼职工作 - 力扣

题目大意

描述：给定 $n$ 个兼职工作，每个工作有开始时间 $startTime[i]$、结束时间 $endTime[i]$ 和报酬 $profit[i]$。

要求：计算最大能获得的报酬总和。每个工作必须在开始时间开始，在结束时间结束。你同一时间只能做一项工作，但可以按任意顺序安排工作（即工作不能重叠，结束时间和开始时间相同可以接续）。

说明：

• $1 \le startTime.length == endTime.length == profit.length \le 5 \times 10^{4}$。
• $1 \le startTime[i] < endTime[i] \le 10^{9}$。
• $1 \le profit[i] \le 10^{4}$。

示例：

• 示例 1：

输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：选择工作 1（1→3，50）和工作 4（3→6，70），报酬总和为 50+70=120。

• 示例 2：

输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输出：150
解释：选择工作 1（1→3，20）、工作 4（4→6，70）和工作 5（6→9，60），报酬总和为 20+70+60=150。

解题思路

思路 1：动态规划 + 二分查找

1. 阶段划分

将 $n$ 个工作按结束时间排序。排序后，按顺序依次考虑每个工作，决定选或不选。阶段就是排序后的工作下标 $i$（从 $1$ 到 $n$）。

按结束时间排序的原因：在考虑第 $i$ 个工作时，我们已经考虑完了所有结束时间早于它的工作，这样我们可以方便地找到与第 $i$ 个工作不冲突的最后一个工作。

2. 定义状态

定义 $dp[i]$ 表示考虑前 $i$ 个工作（即排序后的前 $i$ 个）时能获得的最大报酬。

3. 状态转移方程

对于第 $i$ 个工作，有两种选择：

• 不选第 $i$ 个工作：$dp[i] = dp[i-1]$。
• 选第 $i$ 个工作：先找到"上一个不冲突的工作"——即结束时间 $\le startTime[i]$ 的最后一个工作。假设这个工作的下标为 $j$（如果存在），则选第 $i$ 个工作能得到的报酬为 $dp[j] + profit[i]$。

综合两种情况：

$$dp[i] = \max(dp[i-1], dp[j] + profit[i])$$

其中 $j$ 是满足 $endTime[j] \le startTime[i]$ 的最大下标（使用二分查找在已排序的结束时间数组中查找）。

4. 初始条件

• $dp[0] = 0$（没有工作时报酬为 $0$）。
• 为了方便，下标从 $1$ 开始。

5. 最终结果

$dp[n]$ 即为最大能获得的报酬总和。

6. 结合示例走一遍

$startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]$

按结束时间排序后（正好已经排好序）：

i	startTime	endTime	profit
1	1	3	50
2	2	4	10
3	3	5	40
4	3	6	70

计算 $dp$：

• $dp[0] = 0$
• $i=1$：$start[1]=1$，二分查找结束时间 $\le 1$ 的工作 → 不存在 $(j=0)$
  • 不选：$dp[1]=dp[0]=0$
  • 选：$dp[0]+50=50$
  • $dp[1]=\max(0,50)=50$
• $i=2$：$start[2]=2$，二分查找结束时间 $\le 2$ 的工作 → 不存在 $(j=0)$
  • 不选：$dp[2]=dp[1]=50$
  • 选：$dp[0]+10=10$
  • $dp[2]=\max(50,10)=50$
• $i=3$：$start[3]=3$，二分查找结束时间 $\le 3$ 的工作 → 工作 1（结束时间 $3$，$j=1$）
  • 不选：$dp[3]=dp[2]=50$
  • 选：$dp[1]+40=50+40=90$
  • $dp[3]=\max(50,90)=90$
• $i=4$：$start[4]=3$，二分查找结束时间 $\le 3$ 的工作 → 工作 1（结束时间 $3$，$j=1$）
  • 不选：$dp[4]=dp[3]=90$
  • 选：$dp[1]+70=50+70=120$
  • $dp[4]=\max(90,120)=120$

结果为 $120$。

思路 1：代码

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        # 将三个数组合并并按结束时间排序
        jobs = sorted(zip(endTime, startTime, profit))

        # 提取排序后的结束时间数组（用于二分查找）
        end = [jobs[i][0] for i in range(n)]

        # dp[i] 表示考虑前 i 个工作的最大报酬，dp[0]=0
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            _, s, p = jobs[i - 1]

            # 二分查找：结束时间 <= s 的最大下标
            # 在 end[0..i-2] 中找最后一个 <= s 的位置
            j = bisect_right(end, s, 0, i - 1)  # 返回的是第一个 > s 的位置

            # 不选 vs 选
            dp[i] = max(dp[i - 1], dp[j] + p)

        return dp[n]

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，排序需要 $O(n \log n)$，每个状态转移使用二分查找需要 $O(\log n)$，共 $n$ 次，总时间 $O(n \log n)$。
• 空间复杂度：$O(n)$，需要 $O(n)$ 的空间存储排序后的工作和 dp 数组。

思路 2：基于堆的贪心（选读）

另一种思路是用最小堆维护当前可安排的工作。按时间顺序处理每个工作，将已经结束的工作从堆中移除，但这种方法处理思路 1 中的"不重叠"约束比较绕，不如 DP + 二分查找直观。建议掌握思路 1，这是区间调度类问题的标准解法。