1235. 规划兼职工作
题目描述
共有 n 份兼职，用三个等长数组描述：第 i 份从 startTime[i] 开始，到 endTime[i] 结束，报酬为 profit[i]。
可以挑选任意多份工作来做，但所选工作的时间段不能重叠。如果一份工作在时刻 X 结束，紧接着可以做一份在 X 开始的工作。
返回能获得的最大总报酬。
示例 1
输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] 输出：120
解释：选第 1 份 [1,3] 和第 4 份 [3,6]，报酬 50 + 70 = 120。
示例 2
输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] 输出：150
解释：选第 1、4、5 份，报酬 20 + 70 + 60 = 150。
示例 3
输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] 输出：6
解释：三份都从 1 开始互相重叠，只能选一份，最多 6。
数据范围
1 <= startTime.length == endTime.length == profit.length <= 5 * 10^41 <= startTime[i] < endTime[i] <= 10^91 <= profit[i] <= 10^4
解题思路：按结束时间排序 + DP + 二分
按结束时间排序。设 dp[i] 为只考虑前 i 份工作时的最大报酬。对第 i 份（开始 s、报酬 p）：不做，就是 dp[i]；做，就只能接在“结束时间 ≤ s”的工作后面。因为结束时间有序，用二分 bisect_right(ends, s) 找到这样的工作有 k 份（即前 k 份），收益 dp[k] + p。dp[i+1] = max(dp[i], dp[k] + p)。
为什么正确
dp[i] 是前 i 份（按结束时间排序）工作中选不重叠子集的最大报酬，且对 i 单调不减。
复杂度分析
时间 O(n log n)，空间 O(n)。
易错点
结束时间等于开始时间不算重叠，所以要找“≤ s”，用 bisect_right 而不是 bisect_left。二分范围限制在前 i 份，只按开始时间排序则无法用这个转移。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
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 in range(len(jobs)):
e, s, p = jobs[i]
k = bisect_right(ends, s, 0, i)
dp[i + 1] = max(dp[i], dp[k] + p)
return dp[-1]class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length; int[][] jobs = new int[n][]; for (int i = 0; i < n; i++) jobs[i] = new int[]{endTime[i], startTime[i], profit[i]}; Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
int[] ends = new int[n]; for (int i = 0; i < n; i++) ends[i] = jobs[i][0];
int[] dp = new int[n + 1];
for (int i = 0; i < n; i++) {
int s = jobs[i][1], p = jobs[i][2];
int lo = 0, hi = i; while (lo < hi) { int m = (lo + hi) >>> 1; if (ends[m] <= s) lo = m + 1; else hi = m; } int k = lo;
dp[i + 1] = Math.max(dp[i], dp[k] + p);
}
return dp[n];
}
}class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size(); vector<array<int, 3>> jobs(n); for (int i = 0; i < n; i++) jobs[i] = {endTime[i], startTime[i], profit[i]}; sort(jobs.begin(), jobs.end());
vector<int> ends(n); for (int i = 0; i < n; i++) ends[i] = jobs[i][0];
vector<int> dp(n + 1, 0);
for (int i = 0; i < n; i++) {
int s = jobs[i][1], p = jobs[i][2];
int k = upper_bound(ends.begin(), ends.begin() + i, s) - ends.begin();
dp[i + 1] = max(dp[i], dp[k] + p);
}
return dp[n];
}
};func jobScheduling(startTime []int, endTime []int, profit []int) int {
n := len(startTime); jobs := make([][3]int, n); for i := range jobs { jobs[i] = [3]int{endTime[i], startTime[i], profit[i]} }; sort.Slice(jobs, func(a, b int) bool { return jobs[a][0] < jobs[b][0] })
ends := make([]int, n); for i := range jobs { ends[i] = jobs[i][0] }
dp := make([]int, n+1)
for i := 0; i < n; i++ {
s, p := jobs[i][1], jobs[i][2]
k := sort.Search(i, func(m int) bool { return ends[m] > s })
dp[i+1] = max(dp[i], dp[k]+p)
}
return dp[n]
}var jobScheduling = function(startTime, endTime, profit) {
const jobs = startTime.map((s, i) => [endTime[i], s, profit[i]]).sort((a, b) => a[0] - b[0]);
const ends = jobs.map(j => j[0]);
const dp = new Array(jobs.length + 1).fill(0);
for (let i = 0; i < jobs.length; i++) {
const [e, s, p] = jobs[i];
let lo = 0, hi = i; while (lo < hi) { const m = (lo + hi) >> 1; if (ends[m] <= s) lo = m + 1; else hi = m; } const k = lo;
dp[i + 1] = Math.max(dp[i], dp[k] + p);
}
return dp[jobs.length];
};function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
const jobs = startTime.map((s, i) => [endTime[i], s, profit[i]]).sort((a, b) => a[0] - b[0]);
const ends = jobs.map(j => j[0]);
const dp = new Array(jobs.length + 1).fill(0);
for (let i = 0; i < jobs.length; i++) {
const [e, s, p] = jobs[i];
let lo = 0, hi = i; while (lo < hi) { const m = (lo + hi) >> 1; if (ends[m] <= s) lo = m + 1; else hi = m; } const k = lo;
dp[i + 1] = Math.max(dp[i], dp[k] + p);
}
return dp[jobs.length];
}其他解法
主解法按结束时间排序，用二分在前缀里找最后一个不冲突的工作，是经典的带权区间调度 DP；堆方法按开始时间正向扫描，用堆维护尚未结束的方案。两者复杂度相同，只是寻找可接续的前一份工作的方式不同。
解法 2：按开始时间排序 + 小顶堆 时间 O(n log n)，空间 O(n)
把工作按开始时间排序。维护变量 best，表示已经结束的工作里能取得的最大利润。堆里存放“（结束时间，做完这份工作后的累计利润）”，按结束时间组成小顶堆。处理一份开始于 s 的工作时，先把堆中所有结束时间不晚于 s 的记录弹出并更新 best，这些都是能接在它前面的方案；然后把（结束时间，best + 利润）压入堆。最后把堆弹空，best 就是答案。由于开始时间递增，被弹出的记录对后面的工作同样可用，所以弹出后不再需要。
不需要单独的二分查找，用堆自然地“释放”已结束的工作，是扫描线式的思路。依赖优先队列，在没有内置堆的语言（如 JavaScript）中要手写，常数也比二分稍大。
import heapq
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
jobs = sorted(zip(startTime, endTime, profit))
heap = []
best = 0
for s, e, p in jobs:
while heap and heap[0][0] <= s:
best = max(best, heapq.heappop(heap)[1])
heapq.heappush(heap, (e, best + p))
while heap:
best = max(best, heapq.heappop(heap)[1])
return bestclass Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Integer.compare(startTime[a], startTime[b]));
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
int best = 0;
for (int i : idx) {
while (!heap.isEmpty() && heap.peek()[0] <= startTime[i]) {
best = Math.max(best, heap.poll()[1]);
}
heap.offer(new int[]{endTime[i], best + profit[i]});
}
while (!heap.isEmpty()) {
best = Math.max(best, heap.poll()[1]);
}
return best;
}
}class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
vector<int> idx(n);
for (int i = 0; i < n; i++) idx[i] = i;
sort(idx.begin(), idx.end(), [&](int a, int b) { return startTime[a] < startTime[b]; });
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
int best = 0;
for (int i : idx) {
while (!heap.empty() && heap.top().first <= startTime[i]) {
best = max(best, heap.top().second);
heap.pop();
}
heap.push({endTime[i], best + profit[i]});
}
while (!heap.empty()) {
best = max(best, heap.top().second);
heap.pop();
}
return best;
}
};type endHeap [][2]int
func (h endHeap) Len() int { return len(h) }
func (h endHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h endHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *endHeap) Push(v any) { *h = append(*h, v.([2]int)) }
func (h *endHeap) Pop() any {
old := *h
v := old[len(old)-1]
*h = old[:len(old)-1]
return v
}
func jobScheduling(startTime []int, endTime []int, profit []int) int {
n := len(startTime)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(a, b int) bool { return startTime[idx[a]] < startTime[idx[b]] })
h := &endHeap{}
best := 0
for _, i := range idx {
for h.Len() > 0 && (*h)[0][0] <= startTime[i] {
best = max(best, heap.Pop(h).([2]int)[1])
}
heap.Push(h, [2]int{endTime[i], best + profit[i]})
}
for h.Len() > 0 {
best = max(best, heap.Pop(h).([2]int)[1])
}
return best
}var jobScheduling = function(startTime, endTime, profit) {
const n = startTime.length;
const idx = Array.from({ length: n }, (_, i) => i);
idx.sort((a, b) => startTime[a] - startTime[b]);
const heap = [];
const push = (item) => {
heap.push(item);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l][0] < heap[m][0]) m = l;
if (r < heap.length && heap[r][0] < heap[m][0]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
let best = 0;
for (const i of idx) {
while (heap.length && heap[0][0] <= startTime[i]) {
best = Math.max(best, pop()[1]);
}
push([endTime[i], best + profit[i]]);
}
while (heap.length) {
best = Math.max(best, pop()[1]);
}
return best;
};function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
const n = startTime.length;
const idx = Array.from({ length: n }, (_, i) => i);
idx.sort((a, b) => startTime[a] - startTime[b]);
const heap: number[][] = [];
const push = (item: number[]): void => {
heap.push(item);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = (): number[] => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l][0] < heap[m][0]) m = l;
if (r < heap.length && heap[r][0] < heap[m][0]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
let best = 0;
for (const i of idx) {
while (heap.length && heap[0][0] <= startTime[i]) {
best = Math.max(best, pop()[1]);
}
push([endTime[i], best + profit[i]]);
}
while (heap.length) {
best = Math.max(best, pop()[1]);
}
return best;
}