LeetCode 1235. 规划兼职工作
目录
题目描述
题意分析
每份兼职由开始时间、结束时间和收益三元组描述，同一时刻只能干一份，问最多能挣多少。三个数组按下标一一对应，所以处理前要先把它们绑成一个整体。
「不能同时干两份」在这里的精确含义是：如果接下一份在
t时刻结束的工作，下一份工作的开始时间必须不早于t。题面明确允许一份工作结束的同一时刻开始另一份，这个等号会直接决定后面二分的写法，读题时必须先确认。约束信号有两个。一是每份工作带权重，这意味着「多接几份」不等于「挣得多」，经典的区间贪心（按结束时间贪心地能接就接）在这里不成立；二是工作数量到 $5 \times 10^4$、时间值到 $10^9$，说明要按工作数做 $O(n \log n)$，不能按时间轴展开。
边界情形：所有工作两两重叠时答案就是单份最大收益；所有工作首尾相接时答案是全部收益之和；收益都是正数，所以不存在「接了反而更亏」的情况。
解法：按结束时间排序 + 动态规划 + 二分
核心思路
这是带权区间调度。按结束时间贪心只适用于每个区间价值相同的情况；例如一份收益 100 的长工作与两份各收益 60 的短工作冲突时，贪心选长工作会错过收益 120，因此需要动态规划。
先把工作按结束时间升序排列。对当前工作
(start, end, profit)，所有结束时间不晚于start的工作一定构成前缀，可以用二分一次定位，而不必逐个回看。定义
\[dp[i] = \max(dp[i-1],\ dp[pre] + profit)\]dp[i]为只考虑排序后前i份工作能获得的最大收益，dp[0] = 0。处理第i份工作时设pre为此前结束时间<= start的工作数量，则：第一项表示不选当前工作，第二项表示选当前工作。最优方案对当前工作也只有这两种互斥情况；若选它，前面的选择只能来自可衔接前缀，而
dp[pre]已是该前缀最优值，因此转移既不遗漏也不重复。由前缀归纳可知dp[n]就是全局最优解。
解题步骤
- 将开始时间、结束时间、收益绑定成工作三元组，按结束时间升序排序，并提取有序的
ends数组。- 建立长度为
n + 1的dp；dp[i]对应前i份工作，当前工作因此是jobs[i - 1]。- 在前
i - 1份工作的结束时间中二分查找第一个> start的位置。该位置恰好是可衔接工作的数量pre；使用 upper bound 才会保留end == start的合法衔接。- 用
max(dp[i - 1], dp[pre] + profit)更新dp[i]，最终返回dp[n]。例如工作依结束时间排列为
(1,3,50)、(2,4,10)、(3,5,40)、(3,6,70)。处理(3,5,40)时，结束时间<= 3的工作只有第一份，所以pre = 1，得到max(50, 50 + 40) = 90；处理(3,6,70)时同样接在第一份之后，最终收益为 120。
代码实现
import java.util.Arrays;
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] = startTime[i];
jobs[i][1] = endTime[i];
jobs[i][2] = profit[i];
}
Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1]));
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
ends[i] = jobs[i][1];
}
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int[] job = jobs[i - 1];
int pre = upperBound(ends, i - 1, job[0]);
dp[i] = Math.max(dp[i - 1], dp[pre] + job[2]);
}
return dp[n];
}
private int upperBound(int[] ends, int right, int target) {
int left = 0;
while (left < right) {
int mid = left + (right - left) / 2;
if (ends[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
import "sort"
type Job struct {
start int
end int
profit int
}
func jobScheduling(startTime []int, endTime []int, profit []int) int {
n := len(startTime)
jobs := make([]Job, n)
for i := 0; i < n; i++ {
jobs[i] = Job{start: startTime[i], end: endTime[i], profit: profit[i]}
}
sort.Slice(jobs, func(i, j int) bool {
return jobs[i].end < jobs[j].end
})
ends := make([]int, n)
for i := 0; i < n; i++ {
ends[i] = jobs[i].end
}
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
job := jobs[i-1]
pre := sort.Search(i-1, func(idx int) bool {
return ends[idx] > job.start
})
take := dp[pre] + job.profit
if take > dp[i-1] {
dp[i] = take
} else {
dp[i] = dp[i-1]
}
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O(n \log n)$。排序需要 $O(n \log n)$，
n次状态转移各做一次 $O(\log n)$ 二分。- 空间复杂度：$O(n)$。工作数组、结束时间数组和
dp数组都占线性空间。
关键点总结
- 排序的目的不是方便遍历，而是让每份工作可衔接的候选集合变成一个完整前缀。
dp[i]是前i份工作的最优值，不要求必须选择第i份，因此转移必须同时比较“选”和“不选”。pre表示工作数量，可直接作为dp下标；它不是上一份工作的数组下标。- 题目允许
end == start，所以要找第一个end > start的位置，而不是第一个end >= start的位置。- 面试时先用反例否定无权区间贪心，再给出状态、转移和二分边界，推导会比直接背公式更完整。
易错点总结
- 三个输入数组必须先绑定成三元组再排序，分别排序会破坏同一份工作的对应关系。
- 二分必须使用排序后的
ends，并且只搜索当前工作之前的前缀。- 若用 lower bound 查找
end >= start，会错误排除首尾相接的工作。例如[1,3]和[3,5]应当可以同时选择。- 转移不能只计算
dp[pre] + profit，否则相当于强制选择当前工作，可能覆盖更优的dp[i - 1]。- 线性回扫寻找
pre虽然正确，但整体会退化为 $O(n^2)$，无法通过 $5 \times 10^4$ 的数据规模。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 同样是「排序后选不冲突子集」，但用二分维护尾值 |
| 435. 无重叠区间 | 中等 | 无权重版本，交换论证成立，贪心即可 |
| 646. 最长数对链 | 中等 | 无权重且要求严格衔接，贪心与 DP 两种写法都能过 |
| 1353. 最多可以参加的会议数目 | 中等 | 每份工作只占一天，模型退化成堆维护的贪心 |