C ++中可以参加的最大事件数

假设我们有一个事件数组，其中events [i] = [startDayi，endDayi]。在这里，每个事件我都从startDayi开始，到endDayi结束。我们可以在d的任何天d在startTimei和endTimei（包括两端）中参加事件I。我们必须记住，我们只能在任何时间参加一个活动。因此，找到我们可以参加的最大活动数。因此，例如，如果输入类似于[[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的最大堆创建优先级队列

• 对于我在1到10000范围内

• 从pq中删除元素

• 插入事件[itr，1]

• 增加1

• 而itr <n和events [itr，0] = i

• 当pq不为空并且pq <i的顶部时，

• 如果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