C++动态规划算法：最多可以参加的会议数目

本周推荐阅读

C++二分算法：得到子序列的最少操作次数

本题的其它解法

C++二分算法：最多可以参加的会议数目 II

本文涉及的基础知识点

二分查找算法合集

题目

给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。
你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须完整地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值最大和。
示例 1：
输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。
示例 2：
输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你不需要参加满 k 个会议。
示例 3：
输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。
**参数范围：
1 <= k <= events.length
1 <= k * events.length <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106

分析

上面的代码可以通过，也好理解。就是不够简洁，值转索引用了大约10行。直接先按结束时间排序，然后二分查找。

变量解释

vEndIndexNumToMaxValue[i][k]=j表示，event[0,i][1]结束，完成k个会议的最大价值。假定event[0,j)的结束时间都小于当前开始时间,event[j…)的结束时间都大于或等于当前开始时间。分两种情况：


0==j	只能完成本任务
j>0	参加会议j后，再参加任务i
注意	确保vEndIndexNumToMaxValue[i][k]大于等于vEndIndexNumToMaxValue[i-1][k]，否则就不递增了。递增才能进行二分查找

代码

错误代码一

class Solution {
public:
int maxValue(vector<vector>& events, const int K) {
m_c = events.size();
sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
vector<vector> vEndIndexNumToMaxValue(m_c,vector(K + 1));
int iPreIndex = 0;
for (int i = 0 ; i < m_c ; i++ )
{
const auto& v = events[i];
while ((iPreIndex < m_c) && (events[iPreIndex][1] < v[0]))
{
iPreIndex++;
}
if (0 == iPreIndex)
{
vEndIndexNumToMaxValue[i].assign(K + 1, v[2]);
vEndIndexNumToMaxValue[i][0] = 0;
continue;
}
for (int k = 1; k <= K; k++)
{
vEndIndexNumToMaxValue[i][k] = max(vEndIndexNumToMaxValue[iPreIndex-1][k-1]+v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);
}
}
return vEndIndexNumToMaxValue.back().back();
}
int m_c;
};

错误原因

必须确保vEndIndexNumToMaxValue，k相同时，递增。
注意:

vEndIndexNumToMaxValue[i][0] = 0;

错误代码二

class Solution {
public:
int maxValue(vector<vector>& events, const int K) {
m_c = events.size();
sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
vector<vector> vEndIndexNumToMaxValue(m_c,vector(K + 1));
int iPreIndex = 0;
for (int i = 0 ; i < m_c ; i++ )
{
const auto& v = events[i];
while ((iPreIndex < m_c) && (events[iPreIndex][1] < v[0]))
{
iPreIndex++;
}
for (int k = 1; k <= K; k++)
{
const int iPreMax = (0 == iPreIndex) ? 0 : vEndIndexNumToMaxValue[iPreIndex - 1][k - 1];
vEndIndexNumToMaxValue[i][k] = max(iPreMax +v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);
}
}
return vEndIndexNumToMaxValue.back().back();
}
int m_c;
};

错误原因

开始时间并不是递增的。

正确代码

class Solution {
public:
	int maxValue(vector<vector<int>>& events, const int K) {
		m_c = events.size();
		sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
		vector<vector<int>> vEndIndexNumToMaxValue(m_c,vector<int>(K + 1));
		for (int i = 0 ; i < m_c ; i++ )
		{
			const auto& v = events[i];
			auto it = std::lower_bound(events.begin(), events.end(), v[0], [](const auto& v, int i) {return v[1] < i; });
			const int iLowerIndex = it - events.begin();			
			for (int k = 1; k <= K; k++)
			{
				const int iPreMax = (0 == iLowerIndex) ? 0 : vEndIndexNumToMaxValue[iLowerIndex - 1][k - 1];
				vEndIndexNumToMaxValue[i][k] = max(iPreMax +v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);
			}		
		}	
		return vEndIndexNumToMaxValue.back().back();
	}
	int m_c;
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
vector<vector> events;
int k;
int res;
{
Solution slu;
events = { {53, 55, 77},{37, 56, 58} };
k = 1;
res = slu.maxValue(events, k);
Assert(res, 77);
}
{
Solution slu;
events = { {1,2,4},{3,4,3},{2,3,1} };
k = 2;
res = slu.maxValue(events, k);
Assert(res, 7);
}
{
Solution slu;
events = { {1,2,4},{3,4,3},{2,3,10} };
k = 2;
res = slu.maxValue(events, k);
Assert(res, 10);
}
{
Solution slu;
events = { {1,1,1},{2,2,2},{3,3,3},{4,4,4} };
k = 3;
res = slu.maxValue(events, k);
Assert(res, 9);
}
{
Solution slu;
events = { {21,77,43},{2,74,47},{6,59,22},{47,47,38},{13,74,57},{27,55,27},{8,15,8} };
k = 4;
res = slu.maxValue(events, k);
Assert(res, 57);
}

//CConsole::Out(res);

}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176