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

[@MohdNasir9927]

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

[@ishabharwal1699]

i have the same question. Please do tell if you have found the answer.

[@dayashankarlakhotia4943]

public int jobScheduling (int[]startTime,int[]endTime,int[]profit){ int[][]jobs=new int[startTime.length][3]; fof(int i=0;ia[1]-b[1]); TreeMapmpp=new TreeMap(); mpp.put(0,0); int max=0; for(int[]job:jobs){ int cur=mpp.floorEntry(job[0]).getValue()+job[2]); max=Math.max(max,cur); mpp.put(job[1],max); } return max; } tc=nlogn; sc=0(n);

[@pwjikashishya8883]

same doubt.Please do let me know if you will find the answer

[@ARYANMITTAL]

See, always to prove something is wrong, take a counter example, for ex: 2 jobs [ 9, 20, 3] & [5, 7, 2] - so, job1 is at index0 with start time as 9, while job2 at index1 with start time as 5. Now, if you take job0 then profit is 3, but then you need to search i+1 for a start time of greater than equal to 9, which it won’t be able to find, as next start time i.e. of i+1 is 5. (Forget the skip case, as take case answers the question) Thus, if you don’t want to sort, then don’t do i+1, start back from index 0, but also maintain parallelly that what all index have been visited - so that you don’t re use the already used index. Which will add extra n in both space & time. Thus, best thing is sort, it solves 2 problems, i hope that helps :)

[@MohdNasir9927]

​@@ARYANMITTALThank you so much bhaiya for the great explanation.

[@hemaleka3674]

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

[@muskandebnath6638]

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.

[@akshajjoshy8971]

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

[@sachinvarma9949]

awesome explanation

[@kaushiksen2190]

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

[@reddotcheese]

Great explanation. Good work

[@nishantdehariya5769]

Very nice

[@niteshchoudhary7705]

ThankYou so much for your explanation :-)

[@mohdkhaleeq7468]

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

[@lilgainz]

Bro wo arr 2N lega space bs

[@aditimahabole1761]

nice explanation!

[@lilgainz]

Again killed it bro

[@TON-108]

Bhaiya Please upload Day 3 #100DaysPlacement

[@ARYANMITTAL]

Bro, vo Day2 & Day3, kal ki video me he tha, aaj Day4 aaega, this is because insta pr parallely explanation jaata hai, so we have to go Day by Day, everyday ❤️🫡

[@TON-108]

@@ARYANMITTAL OkOk i got confused 😅

[@FinanceMode14]

Why Start time and not end time?

[@user-vaidesh]

U can also it by using end time and also by using upper bound function

[@sarthakgoel1267]

bhai tum konsi class m ho?

[@harikrushnasuhagiya3925]

killed it bro

[@itsNaveen9]

too much over action ! actually disturbing