資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中可以參加的事件最大數量
假設我們有一個事件陣列，其中 events[i] = [startDayi, endDayi]。這裡每個事件 I 從 startDayi 開始，在 endDayi 結束。我們可以在任何一天 d 參加事件 I，其中 d 在 startTimei 和 endTimei 範圍內（包括兩者）。我們必須記住，我們一次只能參加一個事件。因此，找到我們可以參加的最大事件數。例如，如果輸入類似於 [[1,4], [4,4], [2,2], [3,4], [1,1]]，則輸出將為 1，因為我們可以參加最多四個事件，它們是 [1, 1]、[2, 2]、[3, 4] 和 [4, 4]。
為了解決這個問題，我們將遵循以下步驟：
n := 事件數，然後根據開始日期對事件列表進行排序，設定 ret := 0 和 itr := 0
建立一個基於最大堆的優先順序佇列，稱為 pq
對於 I 範圍從 1 到 10000
當 itr < n 且 events[itr, 0] = i 時
插入 events[itr, 1]
將 itr 增加 1
當 pq 不為空且 pq 的頂部 < i 時，
從 pq 中刪除元素
如果 pq 不為空，則從 pq 中刪除並使 ret 增加 1
返回 ret
示例（C++）
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector <int>& a, vector <int>& b){
return a[0] < b[0];
}
int maxEvents(vector<vector<int>>& events) {
int n = events.size();
sort(events.begin(), events.end(), cmp);
int ret = 0;
int itr = 0;
priority_queue <int, vector <int>, greater <int>> pq;
for(int i = 1; i <= 1e5; i++){
while(itr < n && events[itr][0] == i){
pq.push(events[itr][1]);
itr++;
}
while(!pq.empty() && pq.top() < i) pq.pop();
if(!pq.empty()){
pq.pop();
ret++;
}
}
return ret;
}
};
main(){
vector<vector<int>> v = {{1,4},{4,4},{2,2},{3,4},{1,1}};
Solution ob;
cout << (ob.maxEvents(v));
}輸入
[[1,4],[4,4],[2,2],[3,4],[1,1]]
輸出
4
更新於： 2020年4月29日
766 次瀏覽
廣告