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

[@arthurlewin1952]

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

[@codestorywithMIK]

Thanks a lot ❤️❤️❤️

[@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

[@Vansh-re4jx]

which couse was it

[@souravjoshi2293]

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

[@TheBikerDude2024]

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.

[@sunilsarode152]

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

[@satyamgupta1416]

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.

[@ugcwithaddi]

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

[@satyasanjay1339]

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

[@codestorywithMIK]

Thanks a lot ❤️🙏😇

[@satyasanjay1339]

@@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.

[@codestorywithMIK]

@satyasanjay1339 are you referring to the first part of today’s Leetcode POTD ?

[@satyasanjay1339]

@@codestorywithMIK yes

[@Ramneet04]

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 ❤❤

[@abhinavtomar8518]

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

[@codestorywithMIK]

Thanks a ton ❤️❤️😇

[@ishankiverma9450]

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

[@codestorywithMIK]

Soon Ishanki. Thanks a lot 😇🙏

[@codeyoga]

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

[@amankushwaha8180]

your explanation are very good

[@sourabhbindal774]

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

[@codestorywithMIK]

I feel so happy and proud that we are now able to derive bottom also. Thanks a lot for sharing 😇🙏❤️

[@shoaibakhtar9194]

Best and easy explanation of this question

[@nadeking1530]

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

[@nitinkaplas1532]

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

[@codestorywithMIK]

Means a lot Nitin ❤️❤️😇😇

[@the_only_one9415]

Hello sir, here how we can get intuition of combining all arrays into single vector?

[@chillkro25]

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

[@cocoavlogs6622]

please make for knapsack too 0/1 and unbounded

[@soumyasatish7941]

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.

[@Raj10185]

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

[@soumyasatish7941]

@@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

[@Raj10185]

@@soumyasatish7941 yes you can do but its already binary search so doesn.t matter much O (logn} is best tc

[@shivammaurya5464]

bahut mast explain kiya hai

[@codestorywithMIK]

Means a lot ❤️❤️🙏🙏

[@vishalplayzz2580]

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 ?

[@humanity7880]

Thank you for this amazing explanation!

[@codestorywithMIK]

Thanks a lot for watching 😇❤️

[@tarunsingh6374]

Bhaiya , please try to explain java code also 🤌

[@sidharthdhiman4522]

sir can you also explain time complexity at the end also for more beeter understanding

[@codestorywithMIK]

Sure thing Sidharth. Noted ❤️❤️

[@deepakdass4710]

Thanks sir for great explanation ❤❤

[@chetanyagupta5801]

can we also sort based on end time?

[@siriusblack88]

Great expectation

[@keshavmn7283]

Really good explanation 👍

[@gauravbanerjee2898]

Thanks for the explanation Bhaiya but why did you took result as n+1 ??

[@codestorywithMIK]

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.

[@gauravbanerjee2898]

@@codestorywithMIK Got it thanks a lot for the clarification bhaiya ❤

[@vartikatiwari5203]

Great sir,Keep going

[@AlphaOmega-v7k]

For all those stuck with runtime error-Do not use comparator for sorting use normal sorting that will work fine.

[@sz.110]

La jawaab ❤‍🔥❤‍🔥❤‍🔥

[@yogeshkumarverma2125]

Bhai bohot bohot dhanyawad❤

[@10minutes_cs]

I am always get confused when to late l

[@utsavbarnwal7120]

Such A great Explanation ☺

[@codestorywithMIK]

Thank you so much 😇❤️

[@piyushsrivastava5883]

bhaiya simple knapsack approach kyu nhi lagega

[@zaviyakhurshid9097]

Awesome Explanation

[@codestorywithMIK]

Thanks a lot Zaviya 😊

[@nisarggogate8952]

Awesome explanation!

[@codestorywithMIK]

Thanks a lot Nisarg ❤️❤️❤️

[@deepakarya5310]

sir if we change the result value then we are getting overflow exception

[@bhuppidhamii]

thank you

[@abc-ym4zs]

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]

[@codestorywithMIK]

Hi there, I have started a playlist where I will be teaching comparators, STLs etc. - kzbin.info/aero/PLpIkg8OmuX-KtmrBzx-dAzRDp0xn_Xjls Also, you can see this resource that I have created on Github - github.com/MAZHARMIK/Cpp-STL-Quick-Help

[@AmandeepSingh-uq3wp]

Great Explanation 👍

[@codestorywithMIK]

❤️❤️❤️ thank you Amandeep

[@umeshbisht1054]

Thanku bhaiya ❤

[@shivkumar-og4ow]

bhaiya leetcode contest solution bhi upload kro

[@codestorywithMIK]

Sure Shiv, soon planning

[@Saryupareen]

what an explaination great!!

[@codestorywithMIK]

Thank you so much 😇❤️

[@tanishchordia4813]

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?

[@AlphaOmega-v7k]

don't use comparator fubnction for sorting use normal sorting

[@satvrii]

❤❤❤❤

[@codestorywithMIK]

❤️❤️

[@manashchoudhary744]

Which software u r using

[@satyaprakashtiwari5494]

Thanks for making this

[@codestorywithMIK]

❤️😇😇😇

[@anmolraj5054]

Bro you r gem

[@justgoahead_123]

awesome bro !! : )

[@keertilata20]

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

[@codestorywithMIK]

Awesome 👌✌️

[@wearevacationuncoverers]

This is the only place I get me doubts answered. Thanks mik sir

[@vishalplayzz2580]

nice

[@codestorywithMIK]

Thanks a lot Vishal ❤️

[@cacklouncle]

Badhiya

[@codestorywithMIK]

❤️❤️

[@035-harshitsingh7]

bhaiya aap bottom up approach se kyun nhi btate-- tabular wala form

[@codestorywithMIK]

Hi Harshit, Actually i will cover all ways to solve DP in my DP concepts and Qns playlist - kzbin.info/aero/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt

[@shashanksaurabh6478]

Isn't it a greedy?

[@CodeMode9313]

mast maggaan video ::)

[@VinayKumar-rq5kd]

why did you initiliaze n +1 to result. is it n.

[@codestorywithMIK]

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.

[@bhuppidhamii]

classic dp

[@harshtiwari416]

Bottom Up video????

[@bhartendupant8859]

❤

[@nagmakhan3165]

Phenomenal

[@anshikagupta-l1r]

How this solution is logically wrong? int job(int ind,vector& st, vector& en, vector& p,int end) { if(ind>=st.size())return 0; if(end

[@abhishekverma7604]

bhya mujhe isme fractional knapsack ki vibe aa rhi hai...😂

[@roshangeorge97]

can we use greedy?

[@souravjoshi2293]

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.

[@MakeuPerfect]

bhaiya wo duplicate wala akbar samjhate kya hua bsearch mein

[@codestorywithMIK]

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

[@souravjoshi2293]

@@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 ?

[@souravjoshi2293]

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]

[@debanga3501]

@@codestorywithMIK Ek no explanation

[@MakeuPerfect]

@@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}.

[@AmarjeetKumar-to9ub]

🔥++

[@ChiragWadwa]

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

[@wearevacationuncoverers]

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.

[@ChiragWadwa]

@@wearevacationuncoverers thanks a ton bhay ...but can u tell why my code was failing???

[@ChiragWadwa]

@@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?

[@VedBrahmbhattBEE]

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]

[@user-le6ts6ci7h]

Hey MIk I have been looking for jobs , will you mind giving me a referral at your company.

[@codestorywithMIK]

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.

[@ishabharwal1699]

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

[@Chakss]

Amazing explanation!

[@codestorywithMIK]

Thank you 😊

[@ispyu1514]

Great explanation!

[@ankushdangi3154]

❤❤

[@pavankumareluri9226]

nice

[@codestorywithMIK]

Thank you Pavan ❤️🙏😇