Maximum Number of Events That Can Be Attended

I did this problem too late into the night-

Initially, I thought you could solve this problem by sorting the events (by end time, using start time as a tiebreaker) and greedily attending events in that order. However, that runs into the edge case with [[2,3], [2, 3], [1,4], [1, 4]], where you end up:

attending event [2, 3] at time 2
attending event [2, 3] at time 3
attending event [1, 4] at time 4
missing event [1, 4], however, you could have attended this event at time 1

However, I still believed a greedy approach was optimal. Therefore, I realised you could take a greedy approach at every time stamp; at each timestamp, you would attend the valid event with the earliest end time.

We can make this a reality using a min heap, simply adding end times when we pass the start time and removing end times when we pass them.

Then, if there are still elements inside the min heap, that implies that there exist events we can attend; we thus pop() an element and increment once to our answer.

code

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());

        priority_queue<int, vector<int>, greater<int>> pq;

        int ans = 0;
        for (int i = 0, j = 0; j < events.size() || !pq.empty(); ++i) {
            while (j < events.size() && events[j][0] <= i) {
                pq.push(events[j++][1]);
            }
            while (!pq.empty() && pq.top() < i) {
                pq.pop();
            }
            if (!pq.empty()) {
                pq.pop();
                ++ans;
            }
        }
        return ansh
    }
};

complexity

Time: O(n log(n)) where n is the size of events

Space: O(n)

time taken

26 minutes and 39 seconds

i did this problem too late into the night