Maximum Profit in Job Scheduling | Recursion | Memoization | Leetcode 1235

This is the 5th Video on our Dynamic Programming Playlist.In this video we will try to solve a good and a classic DP problem - Maximum Profit in Job Scheduling (Leetcode 1235)

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases. 
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Maximum Profit in Job Scheduling
Company Tags  : Google, Doordash, Airbnb, Adobe

Approach Summary : It uses memoization and binary search to maximize total profit by selecting non-overlapping jobs based on start times, end times, and profits. The jobScheduling function initializes, sorts, and calls the solve function, which recursively explores job selection scenarios. The getNextIndex function efficiently finds the index of the next job using binary search. The goal is to return the maximum profit for the given jobs.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

 Timelines
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear

[arthurlewin]

Another video another great explanation The way you take us from brute force to optimized solution is phenomenal

[souravjoshi]

The man with magical voice.
Another DP problem made easy. Thank you so much
✌

[aws_handles]

Last year i made a huge mistake of taking a paid course which taught me nothing for my intuition building. This year i will practice on my own and be better at DSA

[TheBikerDude]

Excellent explaining, as always. Kudos to you on making us understand to break complex problems into smaller problems.

[ReenaRote]

This is the best question to learn/refresh every crucial concept: sorting, binary search, and dynamic programming. Nicely explained as usual.

[sunilsarode]

I was stuck on how to find next job and then I saw your video, clean !!

[satyasanjay]

It did not feel like I was solving a hard problem. your explanation is just awsome.

[ugcwithaddi]

Insane explanation. It doesn’t seem Hard anymore 🔥🙌

[abhinavtomar]

Really well explained bro, Doesn't feel it was a hard question. Really impressed the way you explain keep bringing such videos thank you

[codeyoga]

Good question to apply Binary Search and Recursion with Memo. Very nicely explained, keep it up !

[shoaibakhtar]

Best and easy explanation of this question

[satyamgupta]

Instead of binary search we can carry one more variable prev which initialise with 1 and if we are taking any job then we will update prev as per its endtime.

[Ramneet]

I tried this with curr and prev approach but got tle then came to this vedio, we actually use this in approach where we sort in other questions i guess. I was really helpful ❤❤

[nadeking]

As always awesome explanation, where would we go without you lol!

[ishankiverma]

Very nicely explained..i request you to teach some advanced topics in DSA too!!!

[sourabhbindal]

Thanks, MIK Sir here is the Bottom-up solution derived from memoization-

class Solution {
public:
int getIndex(vector<vector<int>>& arr, int val, int l, int r) {
int res = r + 2;
while (l <= r) {
int mid = l + (r - l) / 2;
if (val <= arr[mid][0]) {
res = mid;
r = mid - 1;
} else
l = mid + 1;
}
return res;
}
static bool cmp(vector<int>& a, vector<int>& b) { return a[0] <= b[0]; }

int jobScheduling(vector<int>& startTime, vector<int>& endTime,
vector<int>& profit) {
int n = startTime.size();
vector<vector<int>> arr(n, vector<int>(3, 0));

for (int i = 0; i < n; i++) {
arr[i][0] = startTime[i];
arr[i][1] = endTime[i];
arr[i][2] = profit[i];
}
sort(arr.begin(), arr.end(), cmp);

vector<int> dp(n + 2, 0);

for (int i = n - 1; i >= 0; i--) {
int next = getIndex(arr, arr[i][1], i + 1, n - 1);
int taken = arr[i][2] + dp[next];
int not_taken = dp[i + 1];

dp[i] = max(taken, not_taken);
}
return dp[0];
}
};

[nitinkaplas]

bhai yrr isse tarah question solve kroge tu 1 saal me subscriber i think 1Million + ho jaege 😄

[soumyasatish]

Hello! I have been trying to calculate the next index using the stl lower_bound function from index i+1 till end but keep getting syntax errors for

int next = lower_bound(array.begin() + i + 1, array.end(), array[i][1]) - array.begin();

I know the problem is with array.begin + i + 1 but don't know what to replace it with. Let me know your thoughts on this.

[humanity]

Thank you for this amazing explanation!

[chillkro]

Bhaiya prev name kaa variable bna ke uske basis pr.next job ko take/not take kr lete, ye approach chalega ya nhi, like longest increasing subsequence me prev variable bna ke krte h, pls reply