规划兼职工作
难度:
标签:
题目描述
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 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 * 10^41 <= startTime[i] < endTime[i] <= 10^91 <= profit[i] <= 10^4
代码结果
运行时间: 96 ms, 内存: 28.5 MB
/*
* 思路：
* 1. 使用Java Streams和二分查找来实现动态规划。
* 2. 将工作按结束时间排序，使用streams进行计算。
*/
import java.util.*;
import java.util.stream.*;
class JobSchedulerStream {
static class Job {
int start, end, profit;
Job(int s, int e, int p) {
this.start = s;
this.end = e;
this.profit = p;
}
}
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length;
List<Job> jobs = IntStream.range(0, n)
.mapToObj(i -> new Job(startTime[i], endTime[i], profit[i]))
.sorted(Comparator.comparingInt(job -> job.end))
.collect(Collectors.toList());
int[] dp = new int[n];
dp[0] = jobs.get(0).profit;
for (int i = 1; i < n; i++) {
int includeProfit = jobs.get(i).profit;
int l = binarySearch(jobs, i);
if (l != -1) {
includeProfit += dp[l];
}
dp[i] = Math.max(dp[i - 1], includeProfit);
}
return dp[n - 1];
}
private int binarySearch(List<Job> jobs, int index) {
int low = 0, high = index - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (jobs.get(mid).end <= jobs.get(index).start) {
if (jobs.get(mid + 1).end <= jobs.get(index).start) {
low = mid + 1;
} else {
return mid;
}
} else {
high = mid - 1;
}
}
return -1;
}
}
解释
方法:
该题解采用动态规划加二分搜索的方法求解。首先，将工作按照结束时间排序，以便计算可行解。定义一个数组 dp，其中 dp[i] 表示截至第 i 个工作所能获得的最大利润。通过二分搜索来找到一个最大的 j，使得工作 j 的结束时间小于等于当前工作 i 的开始时间，从而确定在接受当前工作之前能获得的最大利润。对于每个工作 i，我们计算不接受这个工作时的利润 dp[-1]（即上一状态的最大值）与接受这个工作后的总利润 dp[j] + profit[i] 的较大者，更新 dp 数组。最终，dp 数组的最后一个元素将给出接受所有工作的情况下的最大利润。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在解决这个问题时选择使用动态规划加二分搜索的方法，而不是其他算法比如贪心或穷举法？
▷🦆
在动态规划的实现中，dp数组的每个元素dp[i]具体代表什么含义？它是如何从前一个状态dp[i-1]转移过来的？
▷🦆
二分搜索是如何应用于这个问题中的？具体来说，为什么需要通过二分搜索来找到不与当前工作重叠的最近的工作j？
▷🦆
在进行二分搜索时，bisect_right函数的选择是基于什么考虑？使用bisect_left是否可行，两者有何区别？
▷