Maximum Profit in Job Scheduling | Recursion | Memoization | Leetcode 1235
Vložit
- čas přidán 24. 11. 2022
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
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
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/maximum...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
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
Another video another great explanation The way you take us from brute force to optimized solution is phenomenal
Thanks a lot ❤️❤️❤️
The man with magical voice.
Another DP problem made easy. Thank you so much
✌
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
which couse was it
Insane explanation. It doesn’t seem Hard anymore 🔥🙌
I was stuck on how to find next job and then I saw your video, clean !!
This is the best question to learn/refresh every crucial concept: sorting, binary search, and dynamic programming. Nicely explained as usual.
This is the only place I get me doubts answered. Thanks mik sir
Great explanation!
Thank you for this amazing explanation!
Thanks a lot for watching 😇❤️
Great sir,Keep going
Really good explanation 👍
Bhai bohot bohot dhanyawad❤
As always awesome explanation , where would we go without you lol!
Best and easy explanation of this question
Really well explained bro, Doesn't feel it was a hard question. Really impressed the way you explain keep bringing such videos thank you
Thanks a ton ❤️❤️😇
Good question to apply Binary Search and Recursion with Memo. Very nicely explained, keep it up !
La jawaab ❤🔥❤🔥❤🔥
Great expectation
your explanation are very good
Thanks sir for great explanation ❤❤
Awesome explanation!
Thanks a lot Nisarg ❤️❤️❤️
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 ❤❤
Such A great Explanation ☺
Thank you so much 😇❤️
Phenomenal
what an explaination great!!
Thank you so much 😇❤️
Amazing explanation!
Thank you 😊
Bro you r gem
Great Explanation 👍
❤️❤️❤️ thank you Amandeep
Thanku bhaiya ❤
awesome bro !! : )
Thanks for making this
❤️😇😇😇
Awesome Explanation
Thanks a lot Zaviya 😊
bhai yrr isse tarah question solve kroge tu 1 saal me subscriber i think 1Million + ho jaege 😄
Means a lot Nitin ❤️❤️😇😇
thank you
It did not feel like I was solving a hard problem. your explanation is just awsome.
Thanks a lot ❤️🙏😇
@@codestorywithMIK I have a request. can you please make a video on the maximum number of events that can be attended? It is a leetcode medium problem. I couldn't understand its optimal solution.
@satyasanjay1339 are you referring to the first part of today’s Leetcode POTD ?
@@codestorywithMIK yes
bahut mast explain kiya hai
Means a lot ❤️❤️🙏🙏
Very nicely explained..i request you to teach some advanced topics in DSA too!!!
Soon Ishanki. Thanks a lot 😇🙏
❤❤
❤
Badhiya
❤️❤️
Bhaiya , please try to explain java code also 🤌
bhaiya simple knapsack approach kyu nhi lagega
sorting based on ending time giving us wrong answer ?
we will be finding nextind from the current index through binary search
ending time sorting not making sure that it is sorted and starting time sorting making sure it is sorted when finding nxt ind ? is that it ?
❤❤❤❤
❤️❤️
sir if we change the result value then we are getting overflow exception
nice
Thanks a lot Vishal ❤️
can we also sort based on end time?
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
mast maggaan video ::)
For all those stuck with runtime error-Do not use comparator for sorting use normal sorting that will work fine.
🔥++
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.
yes can be done in this way :-
class Solution {
public:
int dp[50004];
vector< pair< int,pair > > arr;
int solve(int i ,vector & starr )
{
//base case
if(i == starr.size())
return 0;
if(dp[i]!= -1) return dp[i];
int nottake = 0 + solve(i+1 ,starr );
int take = -1e9;
int nxt_idx = lower_bound(starr.begin(),starr.end(),arr[i].second.first) - starr.begin();
take = arr[i].second.second + solve(nxt_idx,starr);
return dp[i] = max(take,nottake);
}
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
int n = startTime.size();
// vector dp(n+2,-1);
memset(dp,-1,sizeof(dp));
//sort accng to the start time first
for(int i = 0 ; i < n ; i++)
{
arr.push_back({startTime[i], {endTime[i], profit[i]}});
}
sort(arr.begin(),arr.end());
vectornewArrayIndex;
for(int i=0;i
@@Raj10185 I want the lower_bound function to search from the index after i till end. Trying to reduce the search space for lower_bound
@@soumyasatish7941 yes you can do but its already binary search so doesn.t matter much O (logn} is best tc
I am always get confused when to late l
Which software u r using
sir can you also explain time complexity at the end also for more beeter understanding
Sure thing Sidharth. Noted ❤️❤️
Thanks, MIK Sir here is the Bottom-up solution derived from memoization-
class Solution {
public:
int getIndex(vector& arr, int val, int l, int r) {
int res = r + 2;
while (l
I feel so happy and proud that we are now able to derive bottom also.
Thanks a lot for sharing 😇🙏❤️
classic dp
sir can u i dont know how to write comp function generally we will write as bool comp(auto v1,auto v2)
{
return v1[0]
Hi there,
I have started a playlist where I will be teaching comparators, STLs etc. - czcams.com/play/PLpIkg8OmuX-KtmrBzx-dAzRDp0xn_Xjls.html
Also, you can see this resource that I have created on Github - github.com/MAZHARMIK/Cpp-STL-Quick-Help
can we use greedy?
Let's consider an example to illustrate why a greedy approach may fail for this problem :
Consider the following jobs:
Job: A B C
Start: 1 2 3
End: 3 5 6
Profit:10 5 8
If we sort the jobs by their end times in ascending order, we get:
Job: A B C
Start: 1 2 3
End: 3 5 6
Profit:10 5 8
A greedy approach might consider selecting jobs based on the highest profit at each step. If we follow this greedy strategy, we might select Job A and Job C, as they have the highest profits.
However, the optimal solution is to select Job B and Job C, which results in a total profit of 13. The greedy approach would lead to a suboptimal solution in this case.
bhaiya leetcode contest solution bhi upload kro
Sure Shiv, soon planning
Hello mik , today I tried the exact solution which you taught in the above video but the last testcase gave runtime error. I thought maybe i missed somthing so just copy pasted your solution and your soltuion also gave the runtime error on the last testcase can you help me?
don't use comparator fubnction for sorting use normal sorting
hehe i am so happy i did on my own....
int solve(vector &arr, int ind, vector &dp){
int n=arr.size();
if(ind >= n){
return 0;
}
if(dp[ind] != -1){
return dp[ind];
}
int nxtInd = lower_bound(arr.begin(), arr.end(), vector{arr[ind][1], 0, 0}) - arr.begin();
int take = arr[ind][2] + solve(arr,nxtInd,dp);
int notTake = 0 + solve(arr,ind+1,dp);
return dp[ind] = max(take,notTake);
}
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
int n=startTime.size();
vector arr(n, vector(3, 0)); //{s, e, p}
for(int i = 0; i
Awesome 👌✌️
Thanks for the explanation Bhaiya but why did you took result as n+1 ??
Good qn.
Actually if you notice, whatever index you return from getNextIndex function ,you pass that index in recursion call i.e.
int next = getNextIndex(array, i+1, array[i][1]);
int taken = array[i][2] + solve(array, next);
So, if you get no valid element from getNextIndex , I am returning n+1, because when I will call
int taken = array[i][2] + solve(array, next); (with next = n+1), I will return from the base case
if(i >= n)
return 0;
You can return any invalid value from getNextIndex in case you don't find any valid element BUT, make sure you handle it in base case.
@@codestorywithMIK Got it thanks a lot for the clarification bhaiya ❤
why did you initiliaze n +1 to result. is it n.
Good qn.
Actually if you notice, whatever index you return from getNextIndex function ,you pass that index in recursion call i.e.
int next = getNextIndex(array, i+1, array[i][1]);
int taken = array[i][2] + solve(array, next);
So, if you get no valid element from getNextIndex , I am returning n+1, because when I will call
int taken = array[i][2] + solve(array, next); (with next = n+1), I will return from the base case
if(i >= n)
return 0;
You can return any invalid value from getNextIndex in case you don't find any valid element BUT, make sure you handle it in base case.
bhaiya aap bottom up approach se kyun nhi btate-- tabular wala form
Hi Harshit,
Actually i will cover all ways to solve DP in my DP concepts and Qns playlist - czcams.com/play/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt.html
Bottom Up video????
Isn't it a greedy?
bhya mujhe isme fractional knapsack ki vibe aa rhi hai...😂
bhaiya wo duplicate wala akbar samjhate kya hua bsearch mein
Take this example :
{start, end, profit}
{ {1, 3, 50}, {2, 4, 10}, {3, 5, 40}, {3, 6, 70} }
Suppose you chose to do job 1 - > {1, 3, 50},
Now, you need choose next job whose starting point is >= to ending point of your 1st job {1, 3, 50}
So, you have two options {3, 5, 40}, {3, 6, 70}
Using binary search, the mid might point to {3, 6, 70}, but you need to find the first job which has starting point >= your 1st job end point. That's why if my mid points to {3, 6, 70}, I still try to go left (r = mid-1) and see if we can get more task to left which has starting point >= end point of 1st job
Hope this helps
@@codestorywithMIK Yeah correct.
Since we want to try all possibilities, we don't want to miss {3, 5, 40}
and would try with it and then later try with {3, 6, 70}. Right ?
Or I think we should try to do the dry run for this example , it will help :
[6,15,7,11,1,3,16,2]
[19,18,19,16,10,8,19,8]
[2,9,1,19,5,7,3,19]
@@codestorywithMIK Ek no explanation
@@codestorywithMIK at first mid is pointing to 3/2=1 index then we find the mid is mid+1 to till the end and mid pointing to 5/2=2index,
So mid point to {3,5,40}.
Hey MIk I have been looking for jobs , will you mind giving me a referral at your company.
Hi there,
Unfortunately my company has announced Hiring freeze due to bad market condition.
But feel free to share your resume with me on my email id (you can find email from my github profile), I will try my best to share it with my friends and colleagues to check.
hi can you please tell me whats wrong in my solution?? take condition
class Solution {
public:
int recur(int idx,int last,vector& st, vector& et, vector& profit){
if(idx==profit.size()){return 0;}
int take=0;
if(last
Can Someone tell me why my code is giving overflow runtime error ?
class Solution {
public:
int n, dp[50001];
int getnext(vector& arr, int l, int currentjobend) {
int r = n - 1;
int ans = n + 1;
while (l = currentjobend) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int solve(vector& arr, int i) {
if (i >= n) return 0;
if (dp[i] != -1) return dp[i];
int nextjob = getnext(arr, i + 1, arr[i][1]);
int take = arr[i][2] + solve(arr, nextjob);
int nottake = solve(arr, i + 1);
return dp[i] = max(take, nottake);
}
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
n = startTime.size();
memset(dp, -1, sizeof(dp));
vector arr(n, vector(3, 0));
for (int i = 0; i < n; i++) {
arr[i][0] = startTime[i];
arr[i][1] = endTime[i];
arr[i][2] = profit[i];
}
auto comp = [&](auto& vec1, auto& vec2) { // to sort array based on the starting element
return vec1[0]
pls help me find the start mistake , isme maine lower bound use kia , galat kyu aa rha h , pls help!!!
class Solution {
public:
int getNext(int start,int target,vector &arr){
auto it = lower_bound(arr[0].begin()+start,arr[0].end(),target);
int ind = it - arr[0].begin();
return ind;
}
int solve(int curr,vector &arr,vector &dp){
if(curr >= arr.size()) return 0;
if(dp[curr] != -1) return dp[curr];
//take
int nxt = getNext(curr+1,arr[curr][1],arr);
int take = arr[curr][2] + solve(nxt,arr,dp);
//notTake
int notTake = solve(curr+1,arr,dp);
return dp[curr] = max(take,notTake);
}
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
int n = startTime.size();
vectorarr(n,vector(3));
for(int i=0 ; i
If you want to use lower_bound to find the first job whose starting point is greater than or equal to currentJobEnd, the condition should be vec[0] < currentJobEnd in the lambda function of lower_bound
Something like this :
int getNextIndex(vector& array, int l, int currentJobEnd) {
auto it = lower_bound(array.begin() + l, array.end(), currentJobEnd,
[](const vector& vec, int val) {
return vec[0] < val;
});
return it - array.begin();
}
This will work.
@@wearevacationuncoverers thanks a ton bhay ...but can u tell why my code was failing???
@@wearevacationuncoverers and also can u tell how u exactly wrote this compator thing??? , ive seen miks video of compaator , but still i am not able to get ,, cn u help me out pls?
nice
Thank you Pavan ❤️🙏😇