Keshawn_lu's Blog

Leetcode 1235. 规划兼职工作

动态规划 二分查找
字数统计: 673阅读时长: 3 min
2022/10/22 Share

题目简介：

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

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

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

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

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

示例 1：

sample1_1584

1
2
3
4
5
输入：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。

提示：

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
  • 1 <= startTime[i] < endTime[i] <= 10^9
  • 1 <= profit[i] <= 10^4

思路：

首先按照结束时间对总体进行升序排序。

动态规划，dp[i]代表前i份兼职所能获得的最大报酬，那么对于dp[i]，我们有两种情况：

  • 不选第i份工作，那么dp[i] = dp[i - 1]。
  • 选第i份工作，那么我们需要找到满足endTime[j] <= startTime[i]的最大下标j（即在第 i 份工作开始时间之前结束的最后一份兼职），从而dp[i] = dp[j] + profit[i]。

我们将dp数组总体+1，因此dp[i + 1] + dp[j + 1] + profit[i]。

对于寻找j，我们使用二分查找的库函数upper_bound()，找到第一个满足startTime[i] < endTime[k]的k，则k - 1即为我们需要寻找的j，又因为我们将dp数组整体+1，因此dp[j + 1] = dp[k - 1 + 1] = dp[k]。

最后，转移方程为dp[i + 1] = max(dp[i], dp[k] + profit[i])。

tip:

  • 使用upper_bound()时，需要使用自定义比较函数，即找到第一个满足要求的数字（具体使用方法认知还不够清晰，mark）

代码如下：

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
class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {

        vector<int> dp(startTime.size() + 1);   //前i份工作的最大报酬

        vector<vector<int>> all;

        for(int i = 0; i < startTime.size(); i++){

            all.push_back({startTime[i], endTime[i], profit[i]});
        }

        sort(all.begin(), all.end(), [&](vector<int>& a, vector<int>& b){

            return a[1] < b[1];
        });

        for(int i = 0; i < startTime.size(); i++){

            int pos = upper_bound(all.begin(), all.begin() + i, all[i][0], [&](int start, vector<int>& a){

                return start < a[1];

            }) - all.begin();

            dp[i + 1] = max(dp[i], dp[pos] + all[i][2]);
        }

        return dp[startTime.size()];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网