C++二分查找算法：规划兼职工作-摩杜云开发者社区

题目

你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 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;
 };

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境：

VS2022 C++17

C++二分查找算法：规划兼职工作_规划兼职工作

题目

分析