数据结构
网络
关系数据库管理系统 (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 次浏览
广告