LC 1235. 规划兼职工作

题目描述

这是 LeetCode 上的 1235. 规划兼职工作 ,难度为 困难

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]

给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。

注意,时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。

示例 1:

1
2
3
4
5
6
7
输入: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:

1
2
3
4
5
6
7
输入:startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

输出:150

解释:
我们选择第 145 份工作。
共获得报酬 150 = 20 + 70 + 60

示例 3:

1
2
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 + 二分

为了方便,我们令 startTimestendTimeendTimeprofitps,同时定义三元组 $job[i] = (st[i], et[i], ps[i])$ 来代指某份工作。

我们知道,在理想情况下,若能将所有工作排成不重叠的直线,我们便能通过完成所有工作来取得最大收益。

image.png

归结到每个工作,我们总有「选择完成该工作」和「选择不完成该工作」两种决策。

定义 $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]$。

image.png

此处排序的意义有两点:

  • 由于我们是根据右端点排序,当我们处理到某个 $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 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!