本文涉及的基础知识点
题目
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 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
解释：
我们选择第 1，4，5 份工作。
共获得报酬 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)。至少能完成一份工作，我们枚举最后一份工作。
| 如果没有工作已经结束 | 则只能完成本工作 |
| 如果有工作已完成 | 完成本工作+已经完成工作中报酬最多的工作 |
代码
template<class _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>()); } } }; template<class _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]; }); COrderValueMap<int,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::map<int, 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::map<int, 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 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
