C++에서 참석할 수 있는 최대 이벤트 수

event[i] =[startDayi, endDayi]인 이벤트 배열이 있다고 가정합니다. 여기에서 모든 이벤트는 startDayi에서 시작하여 endDayi에서 끝납니다. 우리는 d가 startTimei와 endTimei(둘 다 포함) 범위에 있는 d일에 이벤트 I에 참석할 수 있습니다. 우리는 한 번에 하나의 이벤트에만 참석할 수 있음을 명심해야 합니다. 따라서 참석할 수 있는 최대 이벤트 수를 찾으십시오. 예를 들어 입력이 [[1,4], [4,4], [2,2], [3,4], [1,1]]과 같으면 출력은 1이 됩니다. 최대 4개의 이벤트에 참석할 수 있습니다. [1, 1], [2, 2], [3, 4] 및 [4, 4].

이 문제를 해결하기 위해 다음 단계를 따릅니다.

n :=이벤트 수, 시작 날짜를 기준으로 이벤트 목록을 정렬하고 ret :=0 및 itr :=0으로 설정
pq
라는 최대 힙을 기반으로 우선 순위 대기열을 만듭니다.
1에서 10000 사이의 I
- 동안 itr
  - 이벤트 삽입[itr, 1]
  - 1만큼 증가
- pq가 비어 있지 않고 pq 의 맨 위에 있는 동안
  - pq에서 요소 삭제
- pq가 비어 있지 않으면 pq에서 삭제하고 ret를 1 증가시킵니다.
리턴 렛

예시(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]]