1353. Maximum Number of Events That Can Be Attended

Description

Solution

Use priority_queue to find the closed DDL’s event and handle it in the day.

There is are tricky programming point that we can directly iterate the whole [earliest start time, latest finish time] to find each day’s best strategy or we can also iterate every sorted event.

Code

class Solution {
    static bool cmp(vector<int>&a, vector<int> &b){
        if(a[0] == b[0])
            return a[1] < b[1];
        return a[0] < b[0];
    }
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), cmp);
        priority_queue<int, vector<int>, greater<>> pq;
        int res = 0, i = 0;
        for(int day = 1; day <= 1E5; day++){
            while(i < events.size() && events[i][0] == day){
                pq.push(events[i++][1]);
            }
            while(!pq.empty() && pq.top() < day)
                pq.pop();
            if(!pq.empty() && pq.top() >= day){
                pq.pop();
                res++;
            }
        }
        // int curt = events[0][0];
        // int res = 0;
        // for(int i = 0; i < events.size(); i++){
        //     if(curt == events[i][0]){
        //         pq.push(events[i][1]);
        //     }else{
        //         while(!pq.empty() && curt < events[i][0]){
        //             curt++;
        //             res++;
        //             pq.pop();
        //             while(!pq.empty() && pq.top() < curt)
        //                 pq.pop();
        //         }
        //         curt = events[i][0];
        //         pq.push(events[i][1]);
        //     }
        // }
        // while(!pq.empty() && pq.top() >= curt){
        //     curt++;
        //     res++;
        //     pq.pop();
        //     while(!pq.empty() && pq.top() < curt)
        //         pq.pop();
        // }
        return res;
    }
};