C++: Two Best Non-Overlapping Events

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        
        // Sort events based on starting time
        sort(events.begin(),events.end());

        // Min heap of {endTime,value}
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

        // Note-1:  We used a min-heap because we need the event with the earliest end time.
        // If the event with the earliest end time overlaps, then all other events will also overlap. 
    
        // Note-2: maxVal should be declared outside the 'for' loop as it stores the maximum value of 
        // non-overlapping interval encountered so far.

        int ans =0;
        int maxVal = 0;
        for(int i=0;i<events.size();i++){

            int startTime = events[i][0];
            int endTime = events[i][1];
            int profit1 = events[i][2];

            // Among all non overlapping event, find the one with best profit.
            while(!pq.empty() && pq.top().first < startTime){
                int profit2 = pq.top().second;
                maxVal = max(maxVal,profit2);
                pq.pop();
            }

            ans = max(ans,maxVal+profit1);
            pq.push({endTime,profit1});
        }
        return ans;
    }
    // Note: Above approach is Greedy approach. This problem can also be solved via DP.
};

class Solution {
public:
    struct event {
        int startTime;
        int endTime;
        int profit;
    };

    static bool cmp(event e1, event e2) { 
        return e1.endTime < e2.endTime;
    }

    // Will use binary search to find the non overlapping event
    // Returns the latest event that ends before the current event starts.
    int srch(vector<event> &vEvent, int idx) {

        int start = 0;
        int end = idx - 1; // As it is 0-based indexing i.e why end=idx-1
        int ans = -1;

        while (start <= end) {

            int mid = (start + end) / 2;
            if (vEvent[mid].endTime < vEvent[idx].startTime) {
                ans = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ans;
    }

    int maxTwoEvents(vector<vector<int>>& events) {

        vector<event> vEvents;
        int noOfEvents = events.size();

        for (int i = 0; i < noOfEvents; i++) {
            vEvents.push_back({events[i][0], events[i][1], events[i][2]});
        }

        // Sorting by endTime ensures that for any event i, all possible non-overlapping
        // events (ending before ith event) appear before it in sorted order.
        sort(vEvents.begin(), vEvents.end(), cmp);

        int t[noOfEvents + 1][3];
        for (int i = 0; i <= noOfEvents; i++) {
            for (int j = 0; j <= 2; j++) {

                // If number of events = 0 OR no elements selected
                if (i == 0 || j == 0)
                    t[i][j] = 0;

                else {
                    int include = vEvents[i - 1].profit;
                    int prevNonOverlappingElement = srch(vEvents, i - 1);

                    // As prevNonOverlappingElement idx will come as zero based. Therefore, dp state 
                    // corresponding to it will be represented by t[prevNonOverlappingElement+1][j-1];
                    if (prevNonOverlappingElement != -1)
                        include += t[prevNonOverlappingElement + 1][j - 1];

                    int exclude = t[i - 1][j];
                    t[i][j] = max(include, exclude);

                    // Note: Above srch may miss a higher-value non-overlapping event & just returns
                    // latest event that ends before the current event starts but the DP accounts 
                    // for it by keeping track of the best value achievable so far.
                }
            }
        }
        return t[noOfEvents][2];
    }
};
    
/*
Golden Note:

1. Sort by endTime when we need to efficiently find the latest non-overlapping event.
2. Sort by startTime when we merge intervals or checking overlaps.
*/