Leetcode - Biweekly Contest 64 (dp probelm)

help
1

preblem - problem link

please help me to find out what I am doing wrong.
my submission

class Solution {
public:
    
    int dp[1000000][3];
    
    
    int findmax(int i, int t, vector<vector<int>>&events, int prev){
        
        if(t==0||i>=events.size()) return 0;
        
        if(dp[i][t]!=-1) return dp[i][t];
        int mx = findmax(i+1,t,events,prev);  // skip the current event
        if(events[i][0]>prev){                // if we are able to attend the current then attend it
            mx = max( mx,   findmax(i+1,t-1,events,events[i][1]) + events[i][2] );
        }
        return dp[i][t] = mx;       
    }
    
    int maxTwoEvents(vector<vector<int>>& events) {
        int n = events.size();
        vector<tuple<int,int,int>> tup;
        
        for(int i=0;i<n;i++){
            tup.push_back({events[i][0],events[i][1],events[i][2]});
        }
        sort(tup.begin(),tup.end());
        
        for(int i=0;i<n;i++){
            events[i][0] = get<0>(tup[i]);
            events[i][1] = get<1>(tup[i]);
            events[i][2] = get<2>(tup[i]);
        }
        
        memset(dp,-1,sizeof(dp));
        int ans = findmax(0,2,events,-1);
        return ans;
        
    }
};
2

How about binary search? Make two arrays, prefix max and suffix max, prefixmax(i) denotes the max value of value among [0,1…i] events with events sorted according to end time. Suffmax(i) denotes the max value among [i,i+1…] Events sorted according to start time.

Now iterate over every event (call this current event) and find premax (j) and suffmax (k)…j and k can be found using binary search (j means the maximum index of event whose end time is less than start time of current event…similar meaning of k), take the maximum of two and add it to value of current event.

3

@shivanshj
ok, got your approach.
but I wanted to solve this problem using DP.
what if there is a constraint that we can attend at most k events, we must have to solve this problem using DP.

so i wanted to find out my mistake, like is my DP state is correct or not.
after thinking a lot I figure out my DP state is not correct.

the correct dp state is :- DP[curr_event][prev_event][t]

let me explain it with an example like, we have total of 5 events we can attend at most 2 events.
right now I am at curr_event = 4, and I have attended 1 event so we have at most 3 possibilities of the previous event (1,2,3) which I am not storing.

am i thinking in right direction or not??

expected space complexity for dp table(DP[curr_event][prev_event][t]) will be
(10^5)*(10^5)*3 = 3(10^10)
that’s why it is not solvable using DP.

4

@bishen28 Well, that’s pretty easy as well :slight_smile: It’s kinda knapsack problem. Sort the events by start time. Dp[i][k] denotes the max value that can be obtained by selecting a subset of event numbered [i , i+1 … n] of size k (Event are numbered from 1 to n in sorted order). Then, dp[i][k] = max( val[i] + dp[j][k-1] , dp[i+1][k]). Here val[i] denotes the value of event i. If I select event i in my subset then I can only select events from [j , j+1…n] where j is smallest event such that start time of event j > end time of event i. (Use binary search to find event j). And if event i is not present in my subset then my availiable subset is [i+1,i+2…n] , hence dp[i+1][k].