1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
private Integer[] memo;
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int[][] jobs = new int[startTime.length][3];
for (int i = 0; i < startTime.length; i++) {
jobs[i][0] = startTime[i];
jobs[i][1] = endTime[i];
jobs[i][2] = profit[i];
}
Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
memo = new Integer[jobs.length];
return backtrack(jobs, 0);
}
private int backtrack(int[][] jobs, int pos) {
if (pos == jobs.length) {
return 0;
}
if (memo[pos] != null) {
return memo[pos];
}
int max = 0;
max = Math.max(backtrack(jobs, pos + 1),
jobs[pos][2] + backtrack(jobs, binarySearch(jobs, pos + 1, jobs[pos][1])));
ans = Math.max(ans, max);
return memo[pos] = max;
}
private int binarySearch(int[][] jobs, int start, int target) {
int left = start, right = jobs.length - 1, ans = jobs.length;
while (left <= right) {
int mid = left + (right - left) / 2;
if (jobs[mid][0] < target) {
left = mid + 1;
} else {
ans = mid;
right = mid - 1;
}
}
return ans;
}
}
|
这道题常规的top-down recursion + memoization就可以了. 但是我设置的递归函数的逻辑有些问题. 我想的是让每个period都作为第一个period, 然后看每个period做第一个的时候, max profit是多少, 之后得到全局最大. 但是这样非常低效. 比如我想知道从第0个period到最后一个period的区间能取到的最大值是多少, 我就让每个period轮流当开头. 于是就变为选第0个period, 然后看第0个period end time后最早开始的period是哪个index, 然后就是求[index, n]的max profit, 然后加上第0个period的profit即可. 然后让第1个period当开头, 然后找比第一个period end time大的最小的start time对应的index是多少, 然后求[index1, n]的max profit即可. 等于是需要一个for循环, 把每一个当前区间内的periods都做一次开头. 这样就会有重复, 比如递归在第一层的时候, 我们可能会尝试求某个区间内的periods, 而递归很深的时候, 我们也可能求同一个区间内的periods. 那么有没有更好的想法呢?
给我们一个区间, 要么第0个periods作为开头, 要么它不作为开头也就是不选它. 因此分成这两种情况. 这样就会好很多, 不需要一个循环了, 而是二叉树. 当我们选一个period的时候, 使用binary search找该period结束时间后start time最早的period的index, 得出该index往后框起来的区间的max profit即可.
时间复杂度: O(nlogn)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int[][] jobs = new int[startTime.length][3];
for (int i = 0; i < startTime.length; i++) {
jobs[i][0] = startTime[i];
jobs[i][1] = endTime[i];
jobs[i][2] = profit[i];
}
Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
int[] dp = new int[jobs.length + 1];
for (int i = dp.length - 2; i >= 0; i--) {
dp[i] = Math.max(dp[i + 1], jobs[i][2] + dp[binarySearch(jobs, i + 1, jobs[i][1])]);
}
return dp[0];
}
private int binarySearch(int[][] jobs, int start, int target) {
int left = start, right = jobs.length - 1, ans = jobs.length;
while (left <= right) {
int mid = left + (right - left) / 2;
if (jobs[mid][0] < target) {
left = mid + 1;
} else {
ans = mid;
right = mid - 1;
}
}
return ans;
}
}
|
根据自顶向下的逻辑, 直接就能写出来转移方程. dp[i]表示的就是从i到最后一个构成的区间的max profit是多少. 根据答案1, 如果binary search找到的是jobs.length, 那么就返回0, 于是我们让dp的长度为jobs.length + 1. 最后一个位置留给pos == jobs.length这种情况. dp的长度对应情况的个数. pos一共有0到jobs.length种取值, 一共是jobs.length + 1种情况, 因此dp声明为这个长度. 然后我们反向遍历. 递归的主要逻辑就是求不取当前区间第一个period的max
以及取当前区间第一个period的max. 那就是dp[i + 1]和jobs[i][2] + dp[binarySearch(jobs, i + 1, jobs[i][1])]看哪个大了. dp[i + 1]表示不取, 后面那个表示取, 于是就要找比该period end time晚的period的最早的start time对应的index是多少, 然后看它到最后一个构成的区间的max是多少.
时间复杂度: O(nlogn) dp中每个元素都会调用binary search. binary search于是就是log1 + log2 + log3 +… +logn, 这就是O(nlogn)
空间复杂度: O(n) 因为有dp数组
