LeetCode_动态规划_困难_1235.规划兼职工作

Bertha 。 2023-10-07 20:33 58阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

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

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

**示例 1：**  
![在这里插入图片描述][ea8ec8d86cf94242a210cd26dbc16d62.png]  
输入：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：**  
![在这里插入图片描述][87144a386ec9461f80d76b3bcc7b5f2d.png]  
输入：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：**  
![在这里插入图片描述][82ff2c44687a4074a37eef1a15910e4e.png]  
输入：startTime = \[1,1,1\], endTime = \[2,3,4\], profit = \[5,6,4\]  
输出：6

**提示：**  
1 <= startTime.length == endTime.length == profit.length <= 5 \* 104  
1 <= startTime\[i\] < endTime\[i\] <= 109  
1 <= profit\[i\] <= 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/maximum-profit-in-job-scheduling

## 2.思路 ##

（1）动态规划 & 二分搜索  
思路参考[本题官方题解][Link 1]。

① 先将将兼职工作按结束时间进行升序排序，定义 dp 数组，**dp\[i\] 表示前 i 份兼职工作可以获得的最大报酬，1 ≤ i ≤ startTime.length。**

int[] dp = new int[startTime.length + 1];

② 状态转移方程如下：

dp[i] = max(dp[i - 1], dp[cnt] + profit[i - 1])

其中，cnt 表示满足结束时间小于等于第 i - 1份工作开始时间的兼职数量，这可以通过二分搜索获得。

## 3.代码实现（Java） ##

//思路1————动态规划 & 二分搜索
    class Solution {
        
        public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        
            int length = startTime.length;
            // jobs[i] 存储第 i 份兼职工作的startTime、endTime、profit
            int[][] jobs = new int[length][3];
            for (int i = 0; i < length; i++) {
        
                jobs[i] = new int[]{
        startTime[i], endTime[i], profit[i]};
            }
            //将兼职工作按结束时间进行升序排序
            Arrays.sort(jobs, (job1, job2) -> job1[1] - job2[1]);
            // dp[i] 表示前 i 份兼职工作可以获得的最大报酬
            int[] dp = new int[length + 1];
            dp[0] = 0;
            for (int i = 1; i <= length; i++) {
        
                // cnt 表示满足结束时间小于等于第 i - 1 份工作开始的兼职工作数量
                int cnt = binarySearchRightBound(jobs, i - 1, jobs[i - 1][0]);
                dp[i] = Math.max(dp[i - 1], dp[cnt] + jobs[i - 1][2]);
            }
            return dp[length];
        }
    
        public int binarySearchRightBound(int[][] jobs, int right, int target) {
        
            int left = 0;
            while (left < right) {
        
                int mid = left + (right - 1 - left) / 2;
                if (jobs[mid][1] > target) {
        
                    right = mid;
                } else {
        
                    left = mid + 1;
                }
            }
            return left;
        }
    }

[ea8ec8d86cf94242a210cd26dbc16d62.png]: https://img-blog.csdnimg.cn/ea8ec8d86cf94242a210cd26dbc16d62.png
[87144a386ec9461f80d76b3bcc7b5f2d.png]: https://img-blog.csdnimg.cn/87144a386ec9461f80d76b3bcc7b5f2d.png
[82ff2c44687a4074a37eef1a15910e4e.png]: https://img-blog.csdnimg.cn/82ff2c44687a4074a37eef1a15910e4e.png
[Link 1]: https://leetcode.cn/problems/maximum-profit-in-job-scheduling/solution/gui-hua-jian-zhi-gong-zuo-by-leetcode-so-gu0e/