Số sự kiện tối đa có thể tham dự trong C ++

Giả sử chúng ta có một mảng sự kiện trong đó các sự kiện [i] =[startDayi, endDayi]. Ở đây mọi sự kiện tôi bắt đầu ở startDayi và kết thúc ở endDayi. Chúng tôi có thể tham dự sự kiện I vào bất kỳ ngày nào trong đó d trong phạm vi startTimei và endTimei (cả hai đều bao gồm). Chúng tôi phải lưu ý rằng chúng tôi chỉ có thể tham dự một sự kiện bất kỳ lúc nào. Vì vậy, hãy tìm số sự kiện tối đa mà chúng tôi có thể tham dự. Vì vậy, ví dụ:nếu đầu vào là [[1,4], [4,4], [2,2], [3,4], [1,1]], thì đầu ra sẽ là 1, vì chúng ta có thể tham dự tối đa bốn sự kiện, đó là [1, 1], [2, 2], [3, 4] và [4, 4].

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• n:=số sự kiện, sau đó sắp xếp danh sách sự kiện dựa trên ngày bắt đầu, đặt ret:=0 và itr:=0

• tạo một hàng đợi ưu tiên dựa trên max-heap được gọi là pq

• cho tôi trong phạm vi từ 1 đến 10000

  • while itr

    • chèn sự kiện [itr, 1]

    • tăng itr lên 1

  • trong khi pq không trống và ở trên cùng của pq

    • xóa phần tử khỏi pq

  • nếu pq không trống, sau đó xóa khỏi pq và tăng ret lên 1

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[[1,4],[4,4],[2,2],[3,4],[1,1]]

Đầu ra

4