蓬莱市建设局网站,手机app开发工资高吗,万网搭建淘宝客网站,住房与城乡建设部网站EPC本文涉及的基础知识点
二分查找算法合集
本题其它解法
C二分向量算法#xff1a;最多可以参加的会议数目 II
题目
给你一个 events 数组#xff0c;其中 events[i] [startDayi, endDayi, valuei] #xff0c;表示第 i 个会议在 startDayi 天开始#xff0c;第 endDay…本文涉及的基础知识点
二分查找算法合集
本题其它解法
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。淘汰后值保持升序。键小的淘汰键大的。
代码
核心代码
templateclass _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());}}};templateclass _Pr1, class _Pr2void 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;}templateclass _Pr1, class _Pr2void 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(vectorvectorint events, int k) {COrderValueMapint, int, true, false mPre;for (const auto v : events){mPre.Add(v[1], v[2]);}while (--k){COrderValueMapint, 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;}
};测试用例
template class T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}template class T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}
}int main()
{vectorvectorint 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);}优化版第一轮不特殊处理
class Solution { public: int maxValue(vectorvector events, int k) { COrderValueMapint, int, true, false mPre; mPre.Add(0, 0); while (k–) { COrderValueMapint, 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; } };
2023年2月旧代码
class Solution { public: int maxValue(vectorvector events, int k) { //dp[i] 已经完成i次会议后的最大值 vector vFinish(k 1, -1); vFinish[0] 0; std::mapint, vector 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(vectorvector 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::mapint,int mEndValue; mEndValue[-1] 0; for (int iK 0; iK k; iK) { std::mapint, int 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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
