Name: Two best non overlapping events
Rating: 4.4 (4258 reviews)
Author: prashantrmishra

Recursive approach: leading to TLE
TC: O(2^n) exponential, since at every max() call we have two choices take or dontTake the current index which makes the time complexity exponential.

SC: O(n) for recursive stack space


class Solution {
    public int maxTwoEvents(int[][] events) {
       Arrays.sort(events,(a,b)-> a[0]-b[0]);
        return max(0,-1,events,2);
    }
    public int max(int index ,int prev, int[][] events, int k){
        //base case
        if(index == events.length) return 0;
        if( k==0) return 0;


        int take  = 0;
        //take
        if(prev ==-1 || events[index][0] > events[prev][1]){
            take = Integer.max(take, events[index][2] + max(index+1,index,events,k-1));
        }
        //dontTake
        int dontTake   = 0 + max(index+1,prev,events,k);

        return Integer.max(take,dontTake);
    }
}

Optimal approach: Memoization
TC: O(nlogn) where log(n) for finding the next valid event using binary search
SC: O(n^2) for using dp array + O(n) auxiliary stack space for recursive call

class Solution {
    public int maxTwoEvents(int[][] events) {
       Arrays.sort(events,(a,b)-> a[0]-b[0]);
        //let try 
       int dp[][] = new int[events.length][3];
       for(int a[] : dp) Arrays.fill(a,-1);
        return max(0,events,2,dp);
    }
    public int max(int index , int[][] events, int k,int dp[][]){
        //base case
        if(index == events.length) return 0;
        if( k==0) return 0;
        if(dp[index][k]!=-1) return dp[index][k];

        int take  = 0;
        //take
       int nextIndex   = findNextIndex(index,events); // or // use this method // find(events[index][1],index+1,events.length-1,events);;
        take = Integer.max(take, events[index][2] + max(nextIndex,events,k-1,dp));

        //dontTake
        int dontTake   = 0 + max(index+1,events,k,dp);

        return  dp[index][k] = Integer.max(take,dontTake);
    }
    public int findNextIndex(int i, int[][] events){
        int low = i+1, high = events.length-1;
        while(low<=high){
            int mid = (low+high)/2;

            if(events[mid][0] > events[i][1]){
                high = mid-1;
            }
            else low  = mid+1;
        }
        return low;
    }
    public int find(int endTime, int low, int high,int events[][]){
        if(high>=low){
            int mid = (low+high)/2;
            if(events[mid][0] > endTime){
                return find(endTime,low,mid-1,events);
            }
            else return find(endTime,mid+1,high,events);
        }
        return low; // we dont have to return -1, since we are not looking for exact value, we are looknig for an event that is just just starts after the endTime only ( since the events are sorted in ascending of start time)
    }
}