anshu2002's blog

Why my friend's solution worked but mine not ?

By anshu2002, history, 9 months ago, In English

for this leetcode problem

this is my solution which gave tle

class Solution {
public:
    vector<vector<int>>dp;
    int solve(int i,vector<vector<int>>&ne,int prev){
        if(i==ne.size()){
            return 0;
        }
        if(prev!=-1 && dp[i][prev]!=-1)
            return dp[i][prev];
        int ans = INT_MIN;
        ans = max(ans,solve(i+1,ne,prev));
        if(prev==-1||ne[prev][1]<=ne[i][0])
            ans = max(ans,solve(i+1,ne,i)+ne[i][2]);
        if(prev!=-1)
            dp[i][prev]=ans;
        return ans;
    }
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        dp = vector<vector<int>>(profit.size(),vector<int>(profit.size(),-1));
        vector<vector<int>>ne;
        for(int i=0;i<profit.size();i++){
            ne.push_back({startTime[i],endTime[i],profit[i]});
        }
        sort(begin(ne),end(ne));
        return solve(0,ne,-1);      
    }
};

and this is my friend's solution which gave AC

class Solution {
public:
    int solve(int ind,int &n,int prevEnd,vector<int> &dp,vector<vector<int>> &v){
        //base case
        if(ind == n){
            return 0;
        }
        if(v[ind][0]<prevEnd){
            return solve(ind+1,n,prevEnd,dp,v);
        }
        //cache
        if(dp[ind] != -1)return dp[ind];
        
        int pick = v[ind][2]+solve(ind+1,n,v[ind][1],dp,v);
        int notPick = 0 + solve(ind+1,n,prevEnd,dp,v);
        
        return dp[ind] = max(pick,notPick);
    }
    
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<vector<int>> v;
        int i,n = endTime.size();
        for(i = 0; i < n; i++){
            v.push_back({startTime[i],endTime[i],profit[i]});
        }
        sort(v.begin(),v.end());
        vector<int> dp(n,-1);
        return solve(0,n,0,dp,v);
    }
};
  • Vote: I like it
  • -23
  • Vote: I do not like it

»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In your solution you have considered both index and prevstate as your states so TC will be index*prevstate that is why it is giving tle.

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Bro u edited your comment before I did , I didn't see that

    bro sorry to make u feel bad but u are wrong . first of all, the second solution of 1d dp works . because , prev ( in my code ) or prevEnd ( in my friends code ) only partially influences the answer . We only need to check whether prev is less then current start . So let's suppose there are two prevends which is less or equal to current start . so the answer for both will be the same . But my code will compute the answer for both the prevends even though the answer will be same thus causing tle .

    → Reply