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)
}
}
Top comments (0)