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);
}
};