C++: Maximum Number of Events That Can Be Attended II

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

    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> &vEvents, 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(vEvents[mid].endTime < vEvents[idx].startTime){

                ans = mid;
                start = mid+1;
            }
            else
                end = mid-1;
        }
        return ans;
    }
    int maxValue(vector<vector<int>>& events, int k) {
        
        int noOfEvents = events.size();

        vector<event> vEvents;
        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][k+1];

        for(int i=0;i<=noOfEvents;i++){

            // If number of events = 0 OR no elements selected
            for(int j=0;j<=k;j++){

                if(i==0 || j==0) 
                    t[i][j]=0;

                else{

                    int include = vEvents[i-1].val;
                    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][k];
    }
};
    
/*
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.
*/