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