C++動態規劃算法：最多可以參加的會議數目

本周推薦閱讀

C++二分算法：得到子序列的最少操作次數

本題的其它解法

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

分析

上面的代碼可以通過，也好理解。就是不夠簡潔，值轉索引用了大約10行。直接先按結束時間排序，然后二分查找。

變量解釋

vEndIndexNumToMaxValue[i][k]=j表示，event[0,i][1]結束，完成k個會議的最大價值。假定event[0,j)的結束時間都小于當前開始時間,event[j…)的結束時間都大于或等于當前開始時間。分兩種情況：


0==j	只能完成本任務
j>0	參加會議j后，再參加任務i
注意	確保vEndIndexNumToMaxValue[i][k]大于等于vEndIndexNumToMaxValue[i-1][k]，否則就不遞增了。遞增才能進行二分查找

代碼

錯誤代碼一

class Solution {
public:
int maxValue(vector<vector>& events, const int K) {
m_c = events.size();
sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
vector<vector> vEndIndexNumToMaxValue(m_c,vector(K + 1));
int iPreIndex = 0;
for (int i = 0 ; i < m_c ; i++ )
{
const auto& v = events[i];
while ((iPreIndex < m_c) && (events[iPreIndex][1] < v[0]))
{
iPreIndex++;
}
if (0 == iPreIndex)
{
vEndIndexNumToMaxValue[i].assign(K + 1, v[2]);
vEndIndexNumToMaxValue[i][0] = 0;
continue;
}
for (int k = 1; k <= K; k++)
{
vEndIndexNumToMaxValue[i][k] = max(vEndIndexNumToMaxValue[iPreIndex-1][k-1]+v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);
}
}
return vEndIndexNumToMaxValue.back().back();
}
int m_c;
};

錯誤原因

必須確保vEndIndexNumToMaxValue，k相同時，遞增。
注意:

vEndIndexNumToMaxValue[i][0] = 0;

錯誤代碼二

class Solution {
public:
int maxValue(vector<vector>& events, const int K) {
m_c = events.size();
sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
vector<vector> vEndIndexNumToMaxValue(m_c,vector(K + 1));
int iPreIndex = 0;
for (int i = 0 ; i < m_c ; i++ )
{
const auto& v = events[i];
while ((iPreIndex < m_c) && (events[iPreIndex][1] < v[0]))
{
iPreIndex++;
}
for (int k = 1; k <= K; k++)
{
const int iPreMax = (0 == iPreIndex) ? 0 : vEndIndexNumToMaxValue[iPreIndex - 1][k - 1];
vEndIndexNumToMaxValue[i][k] = max(iPreMax +v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);
}
}
return vEndIndexNumToMaxValue.back().back();
}
int m_c;
};

錯誤原因

開始時間并不是遞增的。

正確代碼

class Solution {
public:int maxValue(vector<vector<int>>& events, const int K) {m_c = events.size();sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });vector<vector<int>> vEndIndexNumToMaxValue(m_c,vector<int>(K + 1));for (int i = 0 ; i < m_c ; i++ ){const auto& v = events[i];auto it = std::lower_bound(events.begin(), events.end(), v[0], [](const auto& v, int i) {return v[1] < i; });const int iLowerIndex = it - events.begin();			for (int k = 1; k <= K; k++){const int iPreMax = (0 == iLowerIndex) ? 0 : vEndIndexNumToMaxValue[iLowerIndex - 1][k - 1];vEndIndexNumToMaxValue[i][k] = max(iPreMax +v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);}		}	return vEndIndexNumToMaxValue.back().back();}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<vector> events;
int k;
int res;
{
Solution slu;
events = { {53, 55, 77},{37, 56, 58} };
k = 1;
res = slu.maxValue(events, k);
Assert(res, 77);
}
{
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);
}
{
Solution slu;
events = { {21,77,43},{2,74,47},{6,59,22},{47,47,38},{13,74,57},{27,55,27},{8,15,8} };
k = 4;
res = slu.maxValue(events, k);
Assert(res, 57);
}

//CConsole::Out(res);

}

擴展閱讀

視頻課程

有效學習：明確的目標及時的反饋拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176