LeetCode 1235 最大兼职利润 【DP问题】_开始时间,结束时间和收益,求最大收益

题目描述

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

这里有 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。
1
2
3
4
5

示例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。
1
2
3
4
5

提示：

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

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

题解：
对于DP问题还不太熟悉，参考了其他博主的经验，总结了一下该题的解决方法。

首先考虑使用一个结构体jobs将三个属性结合起来（开始时间，结束时间，收益），以结束时间将jobs进行排序，利用递推取得最大的利润。
建立一个DP的map数组，里面存放从递推开始的最大收益，则最终的最大收益在DP数组的最后一个取得。
例如（s,i,p）计算结束时间为i的最大收益 需要 找出i对应的开始时间（包含）之前的最大收益，计算当前的收益cur=P当前工作的利润 +开始时间S之前的最大收益 ，比较DP数组中的最大收益，如果大于DP数组中的最大收益，则更新DP数组即记录dp[i]=cur。迭代完成后，dp数组中最后一个元素就是题中所求。

1.结构化。三个属性结合起来（开始时间，结束时间，收益）

2. 有序化。按照结束时间给工作排序

3.迭代。 开始迭代，更新最大收益数组DP

当前最大收益cur=当前工作收益P+开始时间S之前的最大收益

//upper_bound(job[1])找到第一个比当前开始时间S大的结束时间b
找到S之前的工作：这个结束时间b之前的工作的结束时间d肯定在当前时间S之前
//prev(dp.upper_bound(job[1])) 找到当前开始时间之前的最大收益
//cur = prev(dp.upper_bound(job[1]))->second + job[2];计算结束时间i的最大利润
然后与最大利润数组中最大的数值比较 ，若大于则更新

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
	vector<vector<int>>  jobs(startTime.size(), vector<int>(3));
	for (int i = 0; i<startTime.size(); i++) {
		jobs[i][0] = endTime[i];
		jobs[i][1] = startTime[i];
		jobs[i][2] = profit[i];
	}//结构化，jobs里面的每个元素有三个属性（endTime，startTime，profit）
	sort(jobs.begin(), jobs.end());//排序，按照结束时间对jobs进行排序
	map<int, int>dp;
	dp[0] = 0;//创建最大收益数组
	for (auto job : jobs)//遍历
	{
		int cur = prev(dp.upper_bound(job[1]))->second + job[2];//当前的最大收益
		if (cur>dp.rbegin()->second)
			dp[job[0]] = cur;  //更新DP数组中的最大收益
	}

	return dp.rbegin()->second;//最大收益总在dp数组的最后一个
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

程序参考博客：https://blog.csdn.net/Bob__yuan/article/details/102756819