题目大意：
规划兼职工作
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 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^4
- 1 <= startTime[i] < endTime[i] <= 10^9
- 1 <= profit[i] <= 10^4
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1235
解题思路分析：
典型的递归或者是动态规划的题目。之前的文章多次讲过，动态规划DP与递归加记忆数组两种解法在本质上没有区别。个人认为递归更简单理解一些，因此本题采用递归思想来分析。
为什么这道题会想到递归？换句话说哪些题目应该考虑使用递归思想？递归问题（或者动态规划）的核心是将复杂问题简单化，不容易计算的部分要拆分成子问题，当前计算只考虑当前的情况，其他的计算交给子问题去解决。比如本题，题目给出了一些工作，熊掌和鱼翅不能兼得，我们同时只能接一个私活，因此我们要考虑接下哪一个任务能带给我们的收益最高。对于当前任务，我们有做和不做两种选择，如果选择做，那就意味着获得当前工作报酬的同时，其他与当前任务时间相冲突的任务都要放弃掉，如果选择不做，那么可以在其他任务中挑选一个。
所以当前任务到底是否该做，我们要看全局的利益是否最大化，如果做，那么我们的收益为当前任务的报酬加上余下所有任务的利益最大值（注意余下任务不能包括与当前时间冲突的任务）。如果不做，那么我们的利益应该为除去当前任务外余下任务的利益最大值。我们比较两种选择利益最大的一方为当前的最优选择方案（即知道了当前任务该不该选择）。另外，上面提到的 余下所有任务的利益最大值 即为子问题，也就是递归到下一层时需要解决的问题，子问题的解决方法与当前问题的思路完全一致。递归的终止条件为可选任务为0。
另外本题毕竟是Hard级别，除了想到递归思路之外，还有2个需要注意的点。第一，在选择任务时，如果不对任务的时间进行排序，我们会对时间范围造成混乱，比如，任务1的时间范围是[1, 3]，任务2的时间范围是[6,9]，任务3的时间范围是[2,4]，当我们选择了任务1和2之后，想选择任务3，任务3与任务2的时间不冲突，但可能与其他任务冲突，这样我们需要遍历所有已经执行完的任务查看是否与任务3在时间上有重合，这样效率会非常低。因此我们可以将所有任务按照开始时间进行排序，开始时间大于等于当前任务结束时间的都是下一个可以被选择的对象。
此外第二点需要注意的地方是，如果选择的当前任务，那么下一个可能备选的任务一定是起始时间大于等于自己结束时间的，这里如果暴力找效率也不高，需要考虑到使用二分查找。即使用二分查找找到第一个大于等于当前数的数字。
看下完整实现代码：
Integer[] memo; // 记忆数组
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
memo = new Integer[startTime.length+1]; // 初始化记忆数组
// 为了方便，将三个数组合并成一个
int[][] map = new int[startTime.length][3];
for(int i=0;i<startTime.length;i++){
map[i][0] = startTime[i];
map[i][1] = endTime[i];
map[i][2] = profit[i];
}
// 按照任务的开始时间排序数组
Arrays.sort(map, new Comparator<int[]>() {
public int compare(int[] arr1, int[] arr2) {
return arr1[0] - arr2[0];
}
});
return helper(map,0,0); // 递归找到最优解
}
// map是排序好的数组
// index为当前可以选择任务
// lastEndTime为上一个任务的结束时间
// 返回值为从当前index到结束的所有任务能获得的最大利益
public int helper(int[][] map, int index, int lastEndTime) {
// 当遍历完所有任务时结束递归
if(index>=map.length){
return 0;
}
// 如果记忆数组中存在当前解，直接返回
if(memo[index] != null){
return memo[index];
}
int res=0; // 返回结果
int profit = map[index][2]; // 当前任务的报酬
int endTime = map[index][1]; // 当前任务的结束时间
// 选择当前任务时，可以获得的报酬为：
// 当前任务的报酬，加上下一个可选任务到最后任务间可获得的最大利益
res = profit + helper(map, findNextJob(map, index, endTime), endTime);
// 不选择当前任务时，可以获得的报酬为：
// 下一个可选任务到最后任务间可获得的最大利益
// 选与不选的最大值为返回结果
res = Math.max(res, helper(map, index+1, lastEndTime));
memo[index]=res; // 将结果存入记忆数组
return res;
}
// map是排序好的数组
// currentIndex为最近执行的任务
// lastEndTime为上一个任务（或当前任务）的结束时间
// 返回值为开始时间距离lastEndTime最近的任务下标
private int findNextJob(int[][] map, int currentIndex, int lastEndTime){
// 如果最后一个任务的开始时间都要早于lastEndTime
if(map[map.length-1][0] < lastEndTime){
return map.length; // 返回一个越界的下标
}
// 下面开始常规二分查找
// left为最近执行任务加一，right为最后一个任务
int left=currentIndex+1,right=map.length-1;
int mid;
while(left<right){
mid = (left+right)/2;
if(map[mid][0]<lastEndTime){
left=mid+1;
}else{
right=mid;
}
}
return right;
}本题解法执行时间为25ms。
Runtime: 25 ms, faster than 85.39% of Java online submissions for Maximum Profit in Job Scheduling.
Memory Usage: 51.7 MB, less than 100.00% of Java online submissions for Maximum Profit in Job Scheduling.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1235-maximum-profit-in-job-scheduling-解题思路分析/