C++二分算法：最多可以參加的會議數目 II

本文涉及的基礎知識點

二分查找算法合集

本題其它解法

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;}	
};

測試用例

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);}

優化版：第一輪不特殊處理

class Solution {
public:
int maxValue(vector<vector>& events, int k) {
COrderValueMap<int, int, true, false> mPre;
mPre.Add(0, 0);
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;
}
};

2023年2月舊代碼

class Solution {
public:
int maxValue(vector<vector>& events, int k) {
//dp[i] 已經完成i次會議后的最大值
vector vFinish(k + 1, -1);
vFinish[0] = 0;
std::map<int, 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(vector<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<int,int> mEndValue;
mEndValue[-1] = 0;
for (int iK = 0; iK < k; iK++)
{
std::map<int, 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