Java: Maximum Number of Events That Can Be Attended II

Thought Process

The solution uses Dynamic Programming with binary search to maximize the value of attended events. First, we sort events by endTime to enable efficient searching of non-overlapping events. For each event, we use binary search to find the latest event that doesn't overlap with the current one. The DP table stores the maximum value achievable by attending up to k events. At each step, we choose between including the current event (plus the best non-overlapping solution) or excluding it. Finally, we take the maximum among all possible cases. 

class Event{

    int startTime;
    int endTime;
    int value;

    Event(int start, int end, int profit){

        this.startTime = start;
        this.endTime = end;
        this.value = profit;
    }
}
class Solution {

    // Binary Search
    public int srch(List<Event> allEvents, int event){

        int start = 0;
        int end = event-1;
        int ans = -1;

        while(start<=end){

            int mid = (start+end)/2;
            if(allEvents.get(mid).endTime < allEvents.get(event).startTime){
                ans = mid;
                start = mid+1;
            }
            else
                end = mid-1;
        }
        return ans;
    }
    public int maxValue(int[][] events, int k) {
        
        int noOfEvents = events.length;
        List<Event> allEvents = new ArrayList<>();

        for(int i=0;i<events.length;i++){
            allEvents.add(new Event(events[i][0],events[i][1],events[i][2]));
        }
        // Sort based on End Time
        Collections.sort(allEvents, (a,b)->Integer.compare(a.endTime,b.endTime));

        int[][] maxProfit = new int[noOfEvents+1][k+1];

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

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

                else{

                    int nextPermissibleEvent = srch(allEvents,i-1);
                    int include = allEvents.get(i-1).value;

                    // Note: nextPermissibleEvent+1 is mistake point.
                    // Bec. nextPermissibleEvent idx will come as zero based.
                    if(nextPermissibleEvent!=-1)
                        include += maxProfit[nextPermissibleEvent+1][j-1];

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

                    maxProfit[i][j] = Math.max(include,exclude);
                }
            }
        }
        return maxProfit[noOfEvents][k];
    }
}

Code Complexity

Time Complexity: O(n log n + nk log n)

Sorting takes O(n log n) and DP with binary search takes O(nk log n) where n is number of events and k is maximum events to attend.

Space Complexity: O(nk)

The DP table requires O(nk) space, and sorting requires O(log n) stack space.

Code copied!