本題的其它解法
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(nlogn+knlogn)。第一步時間復雜度O(nlogn)，第二步時間復雜度O(klongn)。
第一步：收集結束時間，排序并除去重復。并給每個結束時間安排索引。
第二步：兩輪循環。
變量解釋
| vEndTime | 結束時間升序并除去重復元素 |
| mEndTimeToIndexs | 結束時間在vEndTime中的順序 |
| vEndTimeIndexToMaxValue | vEndTimeIndexToMaxValue[i]=j 表示，mEndTimeToIndexs[i]結束的會議的最大價值 |
注意
std::prev(it)之前不需要判斷，因為vEndTime中插入了一個比任何開始時間都小的數0。
每輪循環后，要確保vEndTimeIndexToMaxValue升序。
代碼
核心代碼
class Solution {
public:int maxValue(vector<vector<int>>& events, int k) {vector<int> vEndTime = { 0 };for (const auto& v : events){vEndTime.emplace_back(v[1]);}sort(vEndTime.begin(), vEndTime.end());vEndTime.erase(std::unique(vEndTime.begin(), vEndTime.end()), vEndTime.end());unordered_map<int, int> mEndTimeToIndexs;for (int i = 0; i < vEndTime.size(); i++){mEndTimeToIndexs[vEndTime[i]] = i;}vector<int> vEndTimeIndexToMaxValue(vEndTime.size());while (k--){vector<int> dp(vEndTime.size());for (const auto& v : events){int iEndIndex = mEndTimeToIndexs[v[1]];auto it = std::lower_bound(vEndTime.begin(), vEndTime.end(), v[0]);const int iMaxPreIndex = it - 1 - vEndTime.begin() ;const int iMaxValue = vEndTimeIndexToMaxValue[iMaxPreIndex] + v[2];dp[iEndIndex] = max(dp[iEndIndex],iMaxValue);}//使得dp升序int iPreMax = 0;for (auto& n : dp){n = max(n, iPreMax);iPreMax = max(n, iPreMax);}dp.swap(vEndTimeIndexToMaxValue);}return vEndTimeIndexToMaxValue.back();}
};
測試用例
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<vector> 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<int>>& events, int k) {vector<int> vEndTime = { 0 };for (const auto& v : events){vEndTime.emplace_back(v[1]);}sort(vEndTime.begin(), vEndTime.end());vEndTime.erase(std::unique(vEndTime.begin(), vEndTime.end()), vEndTime.end());unordered_map<int, int> mEndTimeToIndexs;for (int i = 0; i < vEndTime.size(); i++){mEndTimeToIndexs[vEndTime[i]] = i;}sort(events.begin(), events.end(), [](const auto& v0, const auto& v1) {return v0[0] < v1[0]; });vector<int> vEndTimeIndexToMaxValue(vEndTime.size());while (k--){vector<int> dp(vEndTime.size());int iPreMax = 0;int iPreIndex = 0;for (const auto& v : events){while ((iPreIndex < vEndTimeIndexToMaxValue.size()) && (vEndTime[iPreIndex] < v[0])){iPreMax = max(iPreMax, vEndTimeIndexToMaxValue[iPreIndex]);iPreIndex++;}int iEndIndex = mEndTimeToIndexs[v[1]];dp[iEndIndex] = max(dp[iEndIndex], iPreMax+v[2]);}dp.swap(vEndTimeIndexToMaxValue); }return *std::max_element(vEndTimeIndexToMaxValue.begin(), vEndTimeIndexToMaxValue.end());}
};
時間復雜度
O(nk)
分析
將events通過開始時間排序后，就可以使用離線查詢。
sort(events.begin(), events.end(), [](const auto& v0, const auto& v1) {return v0[0] < v1[0]; });
iPreMax 記錄了所有結束時間比當前時間小的最大會議價值的最大值。
vEndTimeIndexToMaxValue[0,iPreIndex)的會議價值已經更新到iPreMax。
while ((iPreIndex < vEndTimeIndexToMaxValue.size()) && (vEndTime[iPreIndex] < v[0])){iPreMax = max(iPreMax, vEndTimeIndexToMaxValue[iPreIndex]);iPreIndex++;}
注意: vEndTimeIndexToMaxValue不再升序,所以要：
return *std::max_element(vEndTimeIndexToMaxValue.begin(), vEndTimeIndexToMaxValue.end());
優化二：從開始時間大的處理
代碼
class Solution {
public:int maxValue(vector<vector<int>>& events, int k) {vector<int> vEndTime = { 0 };for (const auto& v : events){vEndTime.emplace_back(v[1]);}sort(vEndTime.begin(), vEndTime.end());vEndTime.erase(std::unique(vEndTime.begin(), vEndTime.end()), vEndTime.end());unordered_map<int, int> mEndTimeToIndexs;for (int i = 0; i < vEndTime.size(); i++){mEndTimeToIndexs[vEndTime[i]] = i;}sort(events.begin(), events.end(), [](const auto& v0, const auto& v1) {return v0[0] > v1[0]; });vector<int> vEndTimeIndexToMaxValue(vEndTime.size());while (k--){int iPreIndex = vEndTimeIndexToMaxValue.size()-1 ;for (const auto& v : events){while ((iPreIndex >=0 ) && (vEndTime[iPreIndex] >= v[0])){ iPreIndex--;}int iEndIndex = mEndTimeToIndexs[v[1]];vEndTimeIndexToMaxValue[iEndIndex] = max(vEndTimeIndexToMaxValue[iEndIndex], vEndTimeIndexToMaxValue[iPreIndex] +v[2]);}//使得dp升序int iPreMax = 0;for (auto& n : vEndTimeIndexToMaxValue){n = max(n, iPreMax);iPreMax = max(n, iPreMax);}}return *std::max_element(vEndTimeIndexToMaxValue.begin(), vEndTimeIndexToMaxValue.end());}
};
分析
時間復雜度O(kn)。
優點
不需要滾動向量，因為更新結束時間大的不會影響開始時間小的。
注意
一，開始時間降序排序。
{return v0[0] > v1[0]; });
二，vEndTimeIndexToMaxValue必須保持升序。
擴展閱讀
視頻課程
有效學習：明確的目標 及時的反饋 拉伸區（難度合適），可以先學簡單的課程，請移步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
| 我想對大家說的話 |
|---|
| 聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。 |
| 子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
----鏈表--兩數相加)
