门户网站登录页面,东莞网站建设网站制作公司,广州seo服务公司,浙江绿建建设计院网站题目
你打算利用空闲时间来做兼职工作赚些零花钱。 这里有 n 份兼职工作#xff0c;每份工作预计从 startTime[i] 开始到 endTime[i] 结束#xff0c;报酬为 profit[i]。 给你一份兼职工作表#xff0c;包含开始时间 startTime#xff0c;结束时间 endTime 和预计报酬 pro…题目
你打算利用空闲时间来做兼职工作赚些零花钱。 这里有 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。 示例 2 输入startTime [1,2,3,4,6], endTime [3,5,10,6,9], profit [20,20,100,70,60] 输出150 解释 我们选择第 145 份工作。 共获得报酬 150 20 70 60。 示例 3 输入startTime [1,1,1], endTime [2,3,4], profit [5,6,4] 输出6 参数范围 1 startTime.length endTime.length profit.length 5 * 10^4 1 startTime[i] endTime[i] 10^9 1 profit[i] 10^4
分析
基础分析
假定先完成工作i再完成j那么start[i]一定小于start[j]所以先对开始时间排序。证明startTime[i] endTime[i] 且endTime[i] startTime[j]。只排序索引就可以了。 mEndTimeToProfit的key对应已完成工作的时间value对应总报酬。如果key0 key1且value0 value1则key2被淘汰。 key1能被选择key0一定能被选择且value0大于等于value1。淘汰后键key和值value都是按升序排序。 由于必定有结果所以无需判断mEndTimeToProfit是否为空由于值也是升序所以返回最后一个元素。
时间复杂度
O(nlogn)。至少能完成一份工作我们枚举最后一份工作。
如果没有工作已经结束则只能完成本工作如果有工作已完成完成本工作已经完成工作中报酬最多的工作
代码
templateclass _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey class COrderValueMap { public: void Add (_Kty iValue, _Ty iNum) { if (!bOutSmallKey) { if (bValueDdes) { Add(iValue, iNum, std::greater_equal_Ty(), std::less_equal_Ty()); } else { Add(iValue, iNum, std::less_equal_Ty(), std::greater_equal_Ty()); } } }; templateclass _Pr1, class _Pr2 void Add(_Kty iValue, _Ty iNum, _Pr1 pr1,_Pr2 pr2 ) { if (!bOutSmallKey) { auto it m_map.upper_bound(iValue); if ((m_map.begin() ! it) pr1(std::prev(it)-second ,iNum)) { return;//被淘汰 } auto ij it; for (; (m_map.end() ! ij) pr2(ij-second , iNum); ij); m_map.erase(it, ij); m_map[iValue] iNum; } }; std::map_Kty, _Ty m_map; };
class Solution { public: int jobScheduling(vector startTime, vector endTime, vector profit) { m_c startTime.size(); vector indexs; for (int i 0; i m_c; i) { indexs.emplace_back(i); } sort(indexs.begin(), indexs.end(), [startTime](const int i1, const int i2) {return startTime[i1] startTime[i2]; }); COrderValueMapint,int,true,false mEndTimeToProfit; for (int i : indexs) { auto it mEndTimeToProfit.m_map.upper_bound(startTime[i]); int iTotalProfit profit[i]; if (mEndTimeToProfit.m_map.begin() ! it) { iTotalProfit std::prev(it)-second; } mEndTimeToProfit.Add(endTime[i], iTotalProfit); } return mEndTimeToProfit.m_map.rbegin()-second; } 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 startTime, endTime, profit; int res; { Solution slu; startTime { 1, 2, 3, 3 }; endTime { 3, 4, 5, 6 }; profit { 50, 10, 40, 70 }; res slu.jobScheduling(startTime, endTime, profit); Assert(120, res); }
//CConsole::Out(res);}
2023年一月旧代码
class Solution { public: int jobScheduling(vector startTime, vector endTime, vector profit) { m_c startTime.size(); vector indexs; for (int i 0; i m_c; i) { indexs.push_back(i); } std::sort(indexs.begin(), indexs.end(), [startTime](const int i1, const int i2) { return startTime[i1] startTime[i2]; }); int iMaxProfit 0; std::mapint, int mEndProfit; for (int i 0; i indexs.size(); i ) { const int index indexs[i]; const int iNewEnd endTime[index]; const int iProfit iMaxProfit profit[index]; if (mEndProfit.count(iNewEnd)) { mEndProfit[iNewEnd] max(mEndProfit[iNewEnd], iProfit); } else { mEndProfit[iNewEnd] iProfit; } if (i 1 indexs.size()) { const int iNextStart startTime[indexs[i 1]]; while (mEndProfit.size() (mEndProfit.begin()-first iNextStart)) { iMaxProfit max(iMaxProfit, mEndProfit.begin()-second); mEndProfit.erase(mEndProfit.begin()); } } } for (auto it : mEndProfit) { iMaxProfit max(iMaxProfit, it.second); } return iMaxProfit; } int m_c; };
2023年8月旧代码
class Solution { public: int jobScheduling(vector startTime, vector endTime, vector profit) { m_c startTime.size(); vector indexs(m_c); iota(indexs.begin(), indexs.end(), 0); sort(indexs.begin(), indexs.end(), [](const int i1, const int i2) { return startTime[i1] startTime[i2]; }); std::mapint, int mEndTotalPro; int iMaxPro 0; for (int i : indexs) { while (mEndTotalPro.size() (mEndTotalPro.begin()-first startTime[i])) { iMaxPro max(iMaxPro, mEndTotalPro.begin()-second); mEndTotalPro.erase(mEndTotalPro.begin()); } const int end endTime[i]; mEndTotalPro[end] max(mEndTotalPro[end], profit[i] iMaxPro); } int iRet 0; for (const auto it : mEndTotalPro) { iRet max(iRet, it.second); } return iRet; } 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
洒家想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。墨家名称的来源有所得以墨记之。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
