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

本周推荐阅读

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

分析

时间复杂度

时间复杂度O(knlogn),两层循环。第一层循环循环k-1次，第二层循环循环n次。循环内部查找、插入、删除O(logn)。

变量解释

mPre 记录的上一轮的完成情况，dp是当前轮的完成情况。键对应的是：结束时间，值对应的是：最大会议价值。如果key0 <= key1且value0 >= value1，那么key0会淘汰key1。能选取key1，一定能选取key0，而value0大于等于value1。淘汰后，值保持升序。键小的淘汰键大的。

代码

核心代码

template<class _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey> 
class COrderValueMap 
{
public:
	void Add (_Kty iValue, _Ty iNum)
	{
		if (bOutSmallKey)
		{
			if (bValueDdes)
			{
				AddOutSmall(iValue, iNum, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
			}
			else
			{
				
			}
		}
		else 
		{
			if (bValueDdes)
			{
				AddNotOutSmall(iValue, iNum, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
			}
			else
			{
				AddNotOutSmall(iValue, iNum, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
			}
		}
	};
	template<class _Pr1, class _Pr2>
	void AddOutSmall(_Kty key, _Ty value, _Pr1 pr1, _Pr2 pr2)
	{
		auto it = m_map.lower_bound(key);
		if ((m_map.end() != it) && pr1(it->second, value))
		{
			return;//被旧值淘汰
		}
		auto ij = it;
		while (it != m_map.begin())
		{
			--it;
			if (pr2(it->second, value))
			{
				it = m_map.erase(it);
			}
		}
		m_map[key] = value;
	}
	template<class _Pr1, class _Pr2>
	void AddNotOutSmall(_Kty key, _Ty value, _Pr1 pr1,_Pr2 pr2 )
	{
		auto it = m_map.upper_bound(key);
		if ((m_map.begin() != it) && pr1(std::prev(it)->second, value))
		{
			return;//被淘汰
		}
		auto ij = it;
		for (; (m_map.end() != ij) && pr2(ij->second, value); ++ij);
		m_map.erase(it, ij);
		m_map[key] = value;
	};
	std::map<_Kty, _Ty> m_map;
};


class Solution {
public:
	int maxValue(vector<vector<int>>& events, int k) {
		COrderValueMap<int, int, true, false> mPre;
		for (const auto& v : events)
		{
			mPre.Add(v[1], v[2]);
		}
		while (--k)
		{
			COrderValueMap<int, int, true, false> dp;
			for (const auto& v : events)
			{
				auto it = mPre.m_map.lower_bound(v[0]);
				int iNewValue = v[2];
				if (mPre.m_map.begin() != it)
				{
					iNewValue += std::prev(it)->second;
				}
				dp.Add(v[1], iNewValue);
			}
			dp.m_map.swap(mPre.m_map);
		}
		return mPre.m_map.rbegin()->second;
	}	
};

  • 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
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

测试用例

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

template <class T>
void Assert(const vector<T>& v1, const vector<T>& 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<int>> events;
	int k;
	int res;
	{
		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);
	}
	
	//CConsole::Out(res);

}

  • 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
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

优化版：第一轮不特殊处理

class Solution {
public:
int maxValue(vector& events, int k) {
COrderValueMap mPre;
mPre.Add(0, 0);
while (k–)
{
COrderValueMap dp;
for (const auto& v : events)
{
auto it = mPre.m_map.lower_bound(v[0]);
int iNewValue = v[2];
if (mPre.m_map.begin() != it)
{
iNewValue += std::prev(it)->second;
}
dp.Add(v[1], iNewValue);
}
dp.m_map.swap(mPre.m_map);
}
return mPre.m_map.rbegin()->second;
}
};

2023年2月旧代码

class Solution {
public:
int maxValue(vector& events, int k) {
//dp[i] 已经完成i次会议后的最大值
vector vFinish(k + 1, -1);
vFinish[0] = 0;
std::map mDoing;
std::sort(events.begin(), events.end(), [](const vector& v1, const vector& v2)
{
return v1[0] < v2[0];
});
for (const auto& v : events)
{
while (mDoing.size() && mDoing.begin()->first < v[0])
{
vector& vDoing = mDoing.begin()->second;
for (int iK = 0; iK <= k; iK++)
{
vFinish[iK] = max(vDoing[iK], vFinish[iK]);
}
mDoing.erase(mDoing.begin());
}
vector& vDoing = mDoing[v[1]];
if (0 == vDoing.size())
{
vDoing.resize(k + 1, -1);
}
for (int iK = 0; iK <= k; iK++)
{
vDoing[iK] = max(vDoing[iK], vFinish[iK]);
if (iK > 0)
{
vDoing[iK] = max(vDoing[iK], vFinish[iK-1] + v[2] );
}
}
}
while (mDoing.size() )
{
vector& vDoing = mDoing.begin()->second;
for (int iK = 0; iK <= k; iK++)
{
vFinish[iK] = max(vDoing[iK], vFinish[iK]);
}
mDoing.erase(mDoing.begin());
}
return *std::max_element(vFinish.begin(), vFinish.end());
}
};

2023年9月旧代码

class Solution {
public:
int maxValue(vector& events, int k) {
m_c = events.size();
vector indexs(m_c);
iota(indexs.begin(), indexs.end(), 0);
sort(indexs.begin(), indexs.end(), [&events](const int& i1, const int& i2)
{
return events[i1][0] < events[i2][0];
});
std::map mEndValue;
mEndValue[-1] = 0;
for (int iK = 0; iK < k; iK++)
{
std::map dp;
for (const auto& i : indexs)
{
auto it = mEndValue.lower_bound(events[i][0]);
const int iPre = (it == mEndValue.begin()) ? 0 : std::prev(it)->second;
const int iNew = iPre + events[i][2];
auto ij = dp.upper_bound(events[i][1]);
if ((ij != dp.begin()) && (std::prev(ij)->second >= iNew))
{
continue;//前面的数值大，再增意义
}
ij = dp.lower_bound(events[i][1]);
auto tmp = ij;
for (; (tmp != dp.end()) && (tmp->second <= iNew); ++tmp);
dp.erase(ij, tmp);
dp[events[i][1]] = iNew;
}
dp.swap(mEndValue);
}
int iMax = 0;
for (const auto& it : mEndValue)
{
iMax = max(iMax, it.second);
}
return iMax;
}
int m_c;
};

扩展阅读

视频课程

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

如何你想快

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

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/134574360"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！