Số Lượng Sự Kiện Tối Đa Có Thể Tham Dự Trong C++

Giả sử mảng events với events[i] = [startDayi, endDayi]. Sự kiện i bắt đầu startDayi và kết thúc endDayi. Ta có thể tham dự sự kiện i tại bất kỳ ngày d nào trong [startDayi, endDayi]. Chỉ có thể tham dự một sự kiện tại một thời điểm. Tìm số lượng sự kiện tối đa có thể tham dự.

Ví dụ: [[1,4],[4,4],[2,2],[3,4],[1,1]] → 4 (tham dự [1,1], [2,2], [3,4], [4,4]).

Để giải quyết, chúng ta làm theo các bước:

• n := số sự kiện, sắp xếp events theo ngày bắt đầu, ret = 0, itr = 0.

• Tạo priority queue min-heap pq.

• Với ngày i từ 1 đến 100000: khi itr < n và events[itr][0] == i: pq.push(events[itr][1]); itr++.

• Khi pq không rỗng và pq.top() < i: pq.pop().

• Nếu pq không rỗng: pq.pop(); ret++.

• Trả về ret.

Ví dụ (C++)

Hãy xem 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;
    }
};

int 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