Please cover this question in one of your videos https://leetcode.com/problems/maximize-the-profit-as-the-salesman/

[ramen-7]

The recursive code I wrote obviously gave TLE but worked

class Solution 
{
    
    int[] dp;
    
    public int solve(List<List<Integer>> arr, int prev_start, int prev_end, int i)
    {
        if(i == arr.size())
            return 0;
        
        
        List<Integer> cur = arr.get(i);
        int start = cur.get(0);
        int end = cur.get(1);
        int taken = 0;
        
        if(start > prev_end)
            taken = cur.get(2) + solve(arr, start, end, i+1);
        int not_taken = solve(arr, prev_start, prev_end, i+1);
        
        return Math.max(taken, not_taken);
            
    }
    
    public int maximizeTheProfit(int n, List<List<Integer>> arr) 
    {
        Collections.sort(arr, (a, b) -> a.get(1) - b.get(1));    
        dp = new int[n];
        Arrays.fill(dp, -1);
        return solve(arr, -1, -1, 0);
    }
}

The dp I tried to make from this did not work, if you could help me figure out why, I'll be grateful :)

class Solution 
{
    
    int[] dp;
    
    public int solve(List<List<Integer>> arr, int prev_start, int prev_end, int i)
    {
        if(i == arr.size())
            return 0;
        
        
        List<Integer> cur = arr.get(i);
        int start = cur.get(0);
        int end = cur.get(1);
        int taken = 0;
         
        if(cur.get(2) < dp[end])
        {
            return dp[end];
        }
            
        
        if(start > prev_end)
            taken = cur.get(2) + solve(arr, start, end, i+1);
        int not_taken = solve(arr, prev_start, prev_end, i+1);
        
        return dp[end] = Math.max(taken, not_taken);
            
    }
    
    public int maximizeTheProfit(int n, List<List<Integer>> arr) 
    {
        Collections.sort(arr, (a, b) -> a.get(1) - b.get(1));    
        dp = new int[n];
        Arrays.fill(dp, -1);
        return solve(arr, 0, 0, 0);
    }
}

[MAZHARMIK]

Hi @ramen-7 ,
Actually this problem is only a Knapsack (take and skip) with a slight optimisation by applying binary search to find next house which can be bought after you buy current house.
See the code below :

`

class Solution {
 
 public:
  
    int N;
     
    int t[100001];

int binary_search(int start, vector<vector<int>>& offers, int target) {
    
    int l = start, r = offers.size()-1;
    int result_idx = -1;
    
    while(l <= r) {
        
        int mid = l + (r-l)/2;
        
        if(offers[mid][0] <= target) {
            l = mid+1;
        } else if(offers[mid][0] > target) {
            result_idx = mid;
            r = mid-1;
        }
    }
    
    return result_idx;
    
}

int solve(int i, vector<vector<int>>& offers) {
    if(i >= offers.size())
        return 0;
    
    if(t[i] != -1)
        return t[i];
    
    //ith customer
    int house_end   = offers[i][1];
    int gold        = offers[i][2];

    int take = gold;
    
    int next_house = binary_search(i+1, offers, house_end); //Find the next valid house you can buy
    
    if(next_house != -1) {
        take += solve(next_house, offers);
    }
    
    int skip = solve(i+1, offers);
    return t[i] = max(take, skip);
}

int maximizeTheProfit(int n, vector<vector<int>>& offers) {
    N = n;
    memset(t, -1, sizeof(t));
    sort(begin(offers), end(offers)); //Because if I take ith house, I need to find the next valid house I can buy (using binary search)
    return solve(0, offers);
}

};

`

[MAZHARMIK]

I will surely make a video on this as well. <3