C++で参加できるイベントの最大数

これを解決するには、次の手順に従います-

• n：=イベントの数、開始日に基づいてイベントリストを並べ替え、ret：=0およびitr：=0

  を設定します。

• pqと呼ばれるmax-heapに基づいて優先キューを作成します

• 1から10000の範囲のIの場合

  • itr

    • イベントを挿入[itr、1]

    • itrを1増やします

  • pqが空ではなく、pqの先頭

    • 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