1235. Maximum Profit in Job Scheduling | DP | Binary Search

In this video, I'll talk about how to solve Leetcode 1235. Maximum Profit in Job Scheduling

Let's Connect:

About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)

✨ Timelines✨
0:00 - Problem Explanation
2:28 - Intuition Building
5:21 - Verifying why it is DP
8:17 - Improving search by Binary Search
10:26 - Recap of entire Flow
14:06 - Code Explanation + Complexity Analysis

✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[MohdNasir]

Bhaiya, why do we have to sort by starttime, I understood that for optimization we have to sort according to the starttime for calculating the lower bound, but without sorting and using the take notTake technique the solution is giving the wrong answer. Why? Can you explain why?

class Solution {
public:
int Recursion(int index, vector<int>& startTime, vector<int>& endTime, vector<int>& profit, int prev, vector<vector<int>>& dp){
if(index >= startTime.size()) return 0;

if(dp[index][prev] != -1) return dp[index][prev];

int take = 0;
if(startTime[index] >= prev)
take = profit[index] + Recursion(index+1, startTime, endTime, profit, endTime[index], dp);
int notTake = Recursion(index+1, startTime, endTime, profit, prev, dp);

return dp[index][prev] = max(take, notTake);
}

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
int maxi = *max_element(endTime.begin(), endTime.end());
vector<vector<int>> dp(n, vector<int>(maxi+1, -1));
return Recursion(0, startTime, endTime, profit, 0, dp);
}
};

[muskandebnath]

Awesome explanation bhaiya... idk for how long i was just skipping this question as i was not able to understand other explanations at the first time. But now I have picked the right video and it cleared all my doubts.

[hemaleka]

All thanks to you now I love programming. Your explanation makes a complex problem easy

[akshajjoshy]

bro u r underrated, I come here for all daily question explanations. Good work bro❣

[kaushiksen]

Ok so the space complexity is O(N)+O(N) right for stack space and dp array space? Thanks for this wonderful explanation bhaiya

[mohdkhaleeq]

how space complexity is O(n) while we are creating 2D array O(n) is for recursion stack space

[niteshchoudhary]

ThankYou so much for your explanation :-)

[TON-]

Bhaiya Please upload Day 3 #100DaysPlacement

[itsNaveen]

too much over action ! actually disturbing