Java: Two Best Non-Overlapping Events

class Solution {
    public int maxTwoEvents(int[][] events) {
        
        // Sort events based on starting time
        Arrays.sort(events,(a,b)->Integer.compare(a[0],b[0]));

        // Min Heap of {endTime,profit}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)-> Integer.compare(a[0],b[0]));

        // 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.length;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.isEmpty() && pq.peek()[0] < startTime){

                int profit2 = pq.peek()[1]; // Profit of Non Overlapping Event
                maxVal = Math.max(maxVal,profit2);
                pq.poll();
            }

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

class Event{

    int startTime;
    int endTime;
    int value;

    Event(int start, int end ,int val){
        this.startTime = start;
        this.endTime = end;
        this.value = val;
    }
}
class Solution {

    // Will use binary search to find the non overlapping event
    // Returns the latest event that ends before the current event starts.
    int srch(List<Event> list, int event){

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

        while(start<=end){

            int mid = (start+end)/2;
            if(list.get(mid).endTime < list.get(event).startTime){
                ans = mid;
                start = mid+1;
            }
            else
                end = mid-1;

        }
        return ans;
    }
    public int maxTwoEvents(int[][] events) {
        
        int noOfEvents = events.length;
        List<Event> list = new ArrayList<>();
        for(int i=0;i<noOfEvents;i++)
            list.add(new Event(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.
        Collections.sort(list, (a,b)->Integer.compare(a.endTime,b.endTime));

        int[][] ans = new int[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)
                    ans[i][j] = 0;

                else{

                    int include = list.get(i-1).value;
                    int prevNonOverlappingEvent = srch(list,i-1);
                    if(prevNonOverlappingEvent!=-1)
                        include += ans[prevNonOverlappingEvent+1][j-1];

                    int exclude = ans[i-1][j];

                    ans[i][j] = Math.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 ans[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.
*/