文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個(gè) events 數(shù)組，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 個(gè)會(huì)議在 startDayi 天開(kāi)始，第 endDayi 天結(jié)束，如果你參加這個(gè)會(huì)議，你能得到價(jià)值 valuei 。
同時(shí)給你一個(gè)整數(shù) k 表示你能參加的最多會(huì)議數(shù)目。

你同一時(shí)間只能參加一個(gè)會(huì)議。如果你選擇參加某個(gè)會(huì)議，那么你必須 完整 地參加完這個(gè)會(huì)議。
會(huì)議結(jié)束日期是包含在會(huì)議內(nèi)的，也就是說(shuō)你不能同時(shí)參加一個(gè)開(kāi)始日期與另一個(gè)結(jié)束日期相同的兩個(gè)會(huì)議。

請(qǐng)你返回能得到的會(huì)議價(jià)值 最大和 。

示例 1：

輸入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2 輸出：7 解釋：選擇綠色的活動(dòng)會(huì)議 0 和 1，得到總價(jià)值和為 4 + 3 = 7 。

示例 2：

輸入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2 輸出：10 解釋：參加會(huì)議 2 ，得到價(jià)值和為 10 。 你沒(méi)法再參加別的會(huì)議了，因?yàn)楦鷷?huì)議 2 有重疊。你 不 需要參加滿 k 個(gè)會(huì)議。

示例 3：

輸入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3 輸出：9 解釋：盡管會(huì)議互不重疊，你只能參加 3 個(gè)會(huì)議，所以選擇價(jià)值最大的 3 個(gè)會(huì)議。提示： 1 <= k <= events.length 1 <= k * events.length <= 10^6 1 <= startDayi <= endDayi <= 10^9 1 <= valuei <= 10^6

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-number-of-events-that-can-be-attended-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• dp[i][k] 表示 遍歷完 第 i 個(gè)會(huì)議，開(kāi)了k次會(huì)，的最大收益
• 按結(jié)束時(shí)間排序
• 對(duì)每個(gè) i 會(huì)議，二分查找前面最近的 無(wú)干涉的會(huì)議 j
• 如果不存在，那么就只能開(kāi)會(huì)議 i
• 如果存在，就從 j 轉(zhuǎn)移到 i，枚舉 次數(shù)
• 還有 i 會(huì)議 不參加，就從 i-1 復(fù)制過(guò)來(lái)

class Solution { public:int maxValue(vector<vector<int>>& events, int k) {sort(events.begin(), events.end(),[&](auto a, auto b){return a[1] < b[1];//結(jié)束時(shí)間排序});int n = events.size();vector<vector<int>> dp(n, vector<int>(k+1, -1));// dp[i][k] 表示 遍歷完 第 i 個(gè)會(huì)議，開(kāi)了k次會(huì)，的最大收益dp[0][0] = 0;dp[0][1] = events[0][2];for(int i = 1; i < n; i++)//轉(zhuǎn)移到i會(huì)議，查找之前可以轉(zhuǎn)移過(guò)來(lái)的j{ // 二分查找時(shí)間不沖突的，最晚的結(jié)束的會(huì)議 jint l = 0, r = i-1, mid, j = n;while(l <= r){mid = l+((r-l)>>1);if(events[mid][1] >= events[i][0])//時(shí)間沖突r = mid-1;else{if(mid==n-1 || events[mid+1][1] >= events[i][0]){j = mid;break;}elsel = mid+1;}}// i 會(huì)議不開(kāi)for(int t = 0; t <= k; ++t)dp[i][t] = max(dp[i][t], dp[i-1][t]);// 沒(méi)有可以轉(zhuǎn)移到 i 的會(huì)議if(j == n) //只能開(kāi)一個(gè)會(huì)議，idp[i][1] = max(dp[i][1], events[i][2]);else // j 可以轉(zhuǎn)移到 i 會(huì)議for(int t = 0; t < k; ++t)//原來(lái)開(kāi)了多少次會(huì){dp[i][t+1] = max(dp[i][t+1], dp[j][t]+events[i][2]);}}int ans = 0;for(int t = 0; t <= k; ++t)ans = max(ans, dp[n-1][t]);return ans;} };

1764 ms 238.1 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1751. 最多可以参加的会议数目 II（DP + 二分查找）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。