C++刷leetcode（1235. 规划兼职工作）【动态规划】
题目描述：你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作，每份工作预计从 startTime 开始到 endTime 结束，报酬为 profit。
给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
示例 1：
输入：startTime = , endTime = , profit =
输出：120
解释：
我们选出第 1 份和第 4 份工作，
时间范围是 +，共获得报酬 120 = 50 + 70。
示例 2：
输入：startTime = , endTime = , profit =
输出：150
解释：
我们选择第 1，4，5 份工作。
共获得报酬 150 = 20 + 70 + 60。
示例 3：
输入：startTime = , endTime = , profit =
输出：6
提示：
1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime < endTime <= 10^9
1 <= profit <= 10^4
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
vector<int>job(n+1);//0的位置作为哨兵，应为“第一个”工作之前没有可比较的工作
iota(job.begin(), job.end(), 0);//生成从0开始连续递增的数列
cout << endl;
sort(job.begin()+1, job.end(), [&](int& a, int& b) {return endTime< endTime; });//按照截止时间进行排序
vector<int>prev(n + 1);
for (int i = 1; i <= n; i++){
for (int j = i - 1; j >= 1; j--){
if (endTime-1] <=startTime-1]){
prev = j;
break;
}
}
}
vector<int>dp(n + 1);
dp = profit-1];
for (int i = 1; i <= n; i++)
dp = max(dp, profit-1] + dp]);
return dp;
}
};
代码来源：https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling/solution/c-dong-tai-gui-hua-xiang-jie-by-csdu-gou/
注意事项：
1.iota：https://blog.csdn.net/qq_40238526/article/details/99341911
2.sort：https://www.cnblogs.com/stones-dream/p/10183210.html
sort(job.begin()+1, job.end(), [&](int& a, int& b) {return endTime< endTime; })这种写法真的好妙！ 这道题代码是取自评论区的，没写出来{:10_266:}
页:
[1]