- 兩個最好的不重疊活動
給你一個下標從 0 開始的二維整數陣列 events ，其中 events[i] = [startTimei, endTimei, valuei] ，第 i 個活動開始于 startTimei ，結束于 endTimei ，如果你參加這個活動，那么你可以得到價值 valuei ，你 最多 可以參加 兩個時間不重疊 活動，使得它們的價值之和 最大 ，
請你回傳價值之和的 最大值 ，
注意，活動的開始時間和結束時間是 包括 在活動時間內的，也就是說，你不能參加兩個活動且它們之一的開始時間等于另一個活動的結束時間，更具體的，如果你參加一個活動，且結束時間為 t ，那么下一個活動必須在 t + 1 或之后的時間開始，
示例 1:
輸入：events = [[1,3,2],[4,5,2],[2,4,3]]
輸出：4
解釋：選擇綠色的活動 0 和 1 ，價值之和為 2 + 2 = 4 ，
示例 2：
Example 1 Diagram
輸入：events = [[1,3,2],[4,5,2],[1,5,5]]
輸出：5
解釋：選擇活動 2 ，價值和為 5 ，
示例 3：
輸入：events = [[1,5,3],[1,5,1],[6,6,5]]
輸出：8
解釋：選擇活動 0 和 2 ，價值之和為 3 + 5 = 8 ，
提示：
2 <= events.length <= 10^5
events[i].length == 3
1 <= startTimei <= endTimei <= 10^9
1 <= valuei <= 10^6
題目思路：
構造陣列
f
[
i
]
f[i]
f[i]表示前i個區間中選擇一個區間能獲得的最大價值
將給定區間按照右端點排序后，遍歷給定區間，列舉第二個區間，再去二分查找比第二個區間小的區間，然后加上其能獲得的最大價值，不斷更新最大價值
class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
int n = events.size();
//陣列下標
vector<int> p(n);
for(int i=0; i<n; ++i){
p[i] = i;
}
//給陣列下標排序，比給vector排序更快
sort(p.begin(),p.end(),[&](int a,int b){
return events[a][1] < events[b][1];
});
int f[n+5]; //f[i]表示前i個區間中選擇一個區間能獲得的最大價值
f[0] = events[p[0]][2];
for(int i=1; i<n; ++i){
f[i] = max(f[i-1],events[p[i]][2]);
}
int res = 0;
//遍歷區間，選擇它作為第二個區間
for(auto &t:events){
int l = 0,r = n;
while(l < r){
//二分尋找最左端點然后減一就是選擇的第一個區間
int mid = (l + r) >> 1;
if(events[p[mid]][1] < t[0]) l = mid;
else r = mid-1;
if(events[p[mid]][1] < t[0]){
l = mid + 1;
}
else if(events[p[mid]][1] > t[0]){
r = mid;
}
else if(events[p[mid]][1] == t[0]){
r = mid;
}
}
int s = t[2];
//保證區間存在，而且區間不重疊
if(l!=0 && events[p[l-1]][1] < t[0]){
s += f[l-1];
}
res = max(res,s);
}
return res;
}
private:
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/388421.html
標籤：其他
上一篇：程式員都在用的5個軟體
下一篇：10月份考研記錄表