题目形容
这是 LeetCode 上的 1235. 布局兼职工作 ，难度为 艰难。
Tag :「序列 DP」、「二分」、「排序」
你打算利用闲暇工夫来做兼职工作赚些零花钱。
这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 完结，报酬为 profit[i]。
给你一份兼职工作表，蕴含开始工夫 startTime，完结工夫 endTime 和预计报酬 profit 三个数组，请你计算并返回能够取得的最大报酬。
留神，工夫上呈现重叠的 2 份工作不能同时进行。
如果你抉择的工作在工夫 X 完结，那么你能够立即进行在工夫 X 开始的下一份工作。
示例 1：
输出：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输入：120
解释：咱们选出第 1 份和第 4 份工作，工夫范畴是 [1-3]+[3-6]，共取得报酬 120 = 50 + 70。示例 2：
输出：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输入：150
解释：咱们抉择第 1，4，5 份工作。共取得报酬 150 = 20 + 70 + 60。示例 3：
输出：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
输入：6提醒：
- $1 <= startTime.length == endTime.length == profit.length <= 5 \times 10^4$
- $1 <= startTime[i] < endTime[i] <= 10^9$
- $1 <= profit[i] <= 10^4$
序列 DP + 二分
为了不便，咱们令 startTime 为 st，endTime 为 endTime，profit 为 ps，同时定义三元组 $job[i] = (st[i], et[i], ps[i])$ 来代指某份工作。
咱们晓得，在现实状况下，若能将所有工作排成不重叠的直线，咱们便能通过实现所有工作来获得最大收益。
归结到每个工作，咱们总有「抉择实现该工作」和「抉择不实现该工作」两种决策。
定义 $f[i]$ 为思考前 $i$ 个工作，所能获得的最大收益（留神 $job[i]$ 不肯定被抉择实现），为了不便，咱们令下标从 $1$ 开始：
- 当不抉择该工作时：因为 $job[i]$ 明确不会产生价值，可知 $f[i] = f[i – 1]$；
-
当抉择该工作时：可分为「仅抉择实现该工作」或「抉择 思考 将该工作接在某个工作前面实现」两种状况：
- 当「仅抉择实现该工作」时，咱们有 $f[i] = job[i][2]$；
-
当「抉择 思考 将该工作接在某个工作前面实现」时，咱们须要在所有满足「$job[j][1] <= job[i][0]$」中抉择最适宜的 $job[j]$ 接在 $job[i]$ 的后面。
即在所有可能在 $job[i]$ 开始前顺利完结的 $job[j]$ 中取最大的 $f[j]$，此时有 $f[i] = f[j] + job[i][2]$须要留神：这里的“接在”是指将 $job[j]$ 纳入思考，但具体计划中，并不一定抉择 $job[j]$ 来执行（好好想想咱们的 $f[i]$ 状态定义）
最终 $f[i]$ 为上述三种计划中的最大值，并且最终的 $f[n]$ 即是咱们的答案。
当咱们解决到 $job[i]$ 时，为了可能「将所有所能拼接在 $job[i]$ 后面的 $job[j]$ 归结到一边」并且「所能更新 $f[i]$ 的 $f[j]$ 均被计算」，咱们能够通过对所有的 $job[i]$ 进行右端点（完结工夫）进行排升序，并依照从小到大的形式解决每个 $job[i]$。
此处排序的意义有两点：
- 因为咱们是依据右端点排序，当咱们解决到某个 $job[i]$ 时，因为有 $job[X][0] < job[X][1]$，因而所能接在 $job[i]$ 后面（完结工夫小于等于 $job[i]$ 开始工夫）的 $job[j]$ 必然位于 $[0, i)$ 之间；
- 因为咱们对 $f[i]$ 的定义并不限定了必须选 $job[i]$，因而在 $[0, i)$ 范畴内以 $job[j]$ 为宰割点的数组的具备「二段性」：坐标范畴小于等于 $j$ 的 $job[X]$ 均可“接在”$job[i]$ 后面。因而咱们可通过「二分」来找所能接在 $job[i]$ 后面的坐标最大的 $job[j]$。
Java 代码：
class Solution {public int jobScheduling(int[] st, int[] et, int[] ps) {
int n = st.length;
List<int[]> list = new ArrayList<>();
for (int i = 0; i < n; i++) list.add(new int[]{st[i], et[i], ps[i]});
Collections.sort(list, (a, b)->a[1] - b[1]);
int[] f = new int[n + 10];
for (int i = 1; i <= n; i++) {int[] info = list.get(i - 1);
int a = info[0], b = info[1], c = info[2];
f[i] = Math.max(f[i - 1], c);
int l = 0, r = i - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (list.get(mid)[1] <= a) l = mid;
else r = mid - 1;
}
if (list.get(r)[1] <= a) f[i] = Math.max(f[i], f[r + 1] + c);
}
return f[n];
}
}TypeScript 代码：
function jobScheduling(st: number[], et: number[], ps: number[]): number {
const n = st.length
const list = new Array<Array<number>>()
for (let i = 0; i < n; i++) list.push([st[i], et[i], ps[i]])
list.sort((a,b)=>a[1]-b[1])
const f = new Array<number>(n + 10).fill(0)
for (let i = 1; i <= n; i++) {const info = list[i - 1]
const a = info[0], b = info[1], c = info[2]
f[i] = Math.max(f[i - 1], c)
let l = 0, r = i - 1
while (l < r) {
const mid = l + r + 1 >> 1
if (list[mid][1] <= a) l = mid
else r = mid - 1
}
if (list[r][1] <= a) f[i] = Math.max(f[i], f[r + 1] + c)
}
return f[n]
}Python 代码：
class Solution:
def jobScheduling(self, st: List[int], et: List[int], ps: List[int]) -> int:
n = len(st)
jobs = [(st[i], et[i], ps[i]) for i in range(n)]
jobs.sort(key=lambda x: x[1])
f = [0] * (n + 10)
for i in range(1, n + 1):
a, b, c = jobs[i - 1]
f[i] = max(f[i - 1], c)
l, r = 0, i - 1
while l < r:
mid = l + r + 1 >> 1
if jobs[mid][1] <= a:
l = mid
else:
r = mid - 1
if jobs[r][1] <= a:
f[i] = max(f[i], f[r + 1] + c)
return f[n]- 工夫复杂度：排序复杂度为 $O(n\log{n})$；
DP过程共有 $n$ 个状态须要转移，每次转移须要进行二分，单次复杂度为 $O(\log{n})$。整体复杂度为 $O(n\log{n})$ - 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1235 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布