Job Sequencing Problem | Greedy Algorithms

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUfo...)
✅Entire Series: bit.ly/placemen...
✅Problem link: practice.geeks...
C++/Java Code: takeuforward.o...
✅Unacademy has launched a subscription that will help you learn and interact with your favorite teacher and will also help you clear your doubts! Check it out here: unacademy.com/.... (use coupon code TAKEUFORWARD to get 10% off)
Join Unacademy's Pinnacle 2021; A Comprehensive and Concise Track to Become an Expert: unacademy.com/...
Check out Unacademy’s Free Classes and tests here (For Desktops):
www.codechef.c...
unacademy.com/...
unacademy.com/...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competiti... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements

[@fritz6600]

It's weird, I was able to get the logic once you visualized everything, I should focus on visualizing my thought process much more or elaborately I guess, thanks a lot!

[@aanchalmittal9897]

You make difficult concepts look easy.... Crystal clear explanation as always ❤

[@vaishnavikammara8047]

I felt so difficult to do this problem, but the way you have explained made it simple to think. 🙌

[@codingwithsmallsteps2878]

Nailed it striver. Thank you for the awesome explanation. The clever part is doing the job (which can be done till very late) on the last deadline unit (if the last deadline unit for the job is not occupied or just as before the last deadline unit which is not occupied) so that in the meantime you can complete the other jobs and maintaining this using a visited array.

[@rahulsarkar913]

Great work dada!! I found a question recently asked in amazon.. Given an integer array arr of size N and an integer S. Return the list of all pairs of elements such that for each sum of elements of each pair equals to S. Note: Each pair should be sorted i.e the first value should be less than or equals to the second value. Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first. Input Format: The first line of input contains two space-separated integers N and S, denoting the size of the input array and the value of S. The second and last line of input contains N space-separated integers, denoting the elements of the input array: arr[i] where 0

[@manideepaktelaprolu3073]

Sort the array and apply 2 pointer technique to find the pairs.

[@yatinarora1252]

It is similar to two sum problem

[@rishabmudliar558]

Instead of sorting method use a frequency array which will make the solution O(n) instead of nlogn with n space complexity

[@pawankumarnandagiri8202]

@@rishabmudliar558 the array elements can be negative so,so we cannot take frequency array

[@VinayKumar-ze2ww]

@@pawankumarnandagiri8202 unordered map is useful then Interviewer can ask for returning indices rather than values, and if we sort array, we won't find the answer

[@diwakarkirar5102]

After solving this question, I came here to look for the best solution and guess what it is what exactly I did, thank you so much for your videos that I am getting better everyday.

[@stith_pragya]

Understood.........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@chandanbera2692]

@TakeUForward As per the explanation, the result array should contain (result[j] = arr[i].id) in line 71 of java code

[@sagargupta7458]

Please continue the playlist..

[@chandan1929]

for correct job sequence put slot[j]=arr[i].id; on line 47 c++ code

[@albedo9617]

Is it wrong if we sort on the basis of deadline but for equal deadlines we sort on the basis of profit. That way we'll be able to finish the jobs that are expiring first but also accepting the jobs that have more profit first.

[@pratikjain3323]

Your explanation skills are insane!! Thanks a ton. :)

[@yutaitadori7318]

Yes🙃

[@avikmallick2493]

instead of disjoint set u can use normal set too to it in nlogn

[@jakeperalta8135]

In c++ code shouldn't we store arr[i].index in slot[j] according to solution explained earlier?

[@shubhamsood1406]

We can do that also, we only have to change the array value from -1 to any other number, both ways of changing the array value is correct.

[@manavshah7450]

Yes. That would be better if they ask u to print the job sequence.

[@mdshokeenkhan242]

let's consider the case after sorting job id deadline profit 2 3 a[j=3] 500 4 3 a[j=2] 400 2 3 a[j=1] 300 1 3 j=3 to1 200 from here you starting the j =3 loop till 1 but in array 3,2,1 index already filled 2 5 -> 100 This is the max deadline case so in next i th iteration you filled this in array 2 1 50 but in this case profit, 200 skips and 100 is considered instead of 200 this is fine ?

[@alokdwivedi2]

yeah

[@venkateshvenky2880]

100 is having enough time to solve later , so is included.

[@ilikememes9052]

I can't even solve this easy question on my own. I have to watch the video for almost every single problem on SDE sheet 😔 I want to be SDE in a big tech company but now losing hope. 😢

[@shadaabiqbal4875]

This is a hard level question not easy

[@varunmanchanda3972]

Bhaiya, I was trying to solve it using DSU but I am not getting a correct answer. Can you please make a video on it if possible?

[@_inspireverse___]

Can we solve it using knapsack method if we sort by deadline in ascending order?

[@mdshokeenkhan242]

in the question's example, we are not performing the job on the deadline which is not given, and in the video answers to deadline 3 are not given but we are performing the job on day 3 ...this is something that question changes???

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

[@mrinmoyhalder7293]

suppose if there are 5 jobs and all have deadline 5, and 5 is the maximum deadline among all, then for each and every deadline we've to check like this - 1+2+3+4+......(n-1) = O(n^2), isn't it

[@abhijitkumarsinha]

yes, you are right !! i was thinking the same

[@tusharsharma6712]

I was expecting priority queue solution from you for O(NlogN) time complexity

[@neerajchoudhary3709]

usko samjh hi nahi aya hoga .lol

[@devrajgoswami4357]

@@neerajchoudhary3709 you probably don't know who he's

[@supriyamanna715]

@@devrajgoswami4357 He's what he is! Striver_79

[@simitoor1]

did u get the solution in this time complexity

[@supriyamanna715]

@@simitoor1 I think MinHeap would do that

[@devanshupadhyay2658]

best video ,related to greedy on the internet.

[@Dharmik_Vibes]

way of explanation is good but code is complicate. shradha khapra code is more crisp and short .and more easy to understand but dp series is amazing

[@tombrady7390]

since we know that values will be integers can we use a stable non comparison based sorting algorithm and bring sorting complexity down to linear

[@anishkumargiri9490]

I have done like this in C language - #include #include #include typedef enum{true,false}bool; typedef struct{ char id; int deed; int profit; }job; int deed(const void *p1 , const void *p2){ const job *pa=p1; const job *pb=p2; return pb->deed - pa->deed; } int compare(const void *p1 , const void *p2){ const job *pa=p1; const job *pb=p2; return pb->profit - pa->profit; } int funC(int max,bool a[]){ int i=0; if(max>1){ for(i=max-1;i>=0;i--){ if(a[i]==false){ return i+1; } } } return 0; } int main() { job arr[]={{'a',2,40},{'b',2,30},{'c',4,20},{'d',1,70}}; int size=sizeof(arr)/sizeof(arr[0]); qsort(arr,size,sizeof(arr[0]),deed); int max=arr[0].deed; qsort(arr,size,sizeof(arr[0]),compare); for(int i=0;i

[@hassanmohammed904]

Hey Striver, Can you upload a video on Roti-Prata Spoj problem please? Thanks in advance !!

[@abhimanyu6534]

Which approach does interviewer asks The one that you taught or the disjoint set approach

[@ankitgarg3247]

I wrote the same code.. but it is giving runtime error on GFG. Can anybody point out the mistake? class Solution { public: static bool sort_arr(Job a, Job b) { return a.profit >= b.profit; } //Function to find the maximum profit and the number of jobs done. vector JobScheduling(Job arr[], int n) { sort(arr, arr+n, sort_arr); int size = arr[0].dead; for(int i=1; i

[@divyasreedev6460]

For the sort_arr function, return "a.profit > b.profit" instead of "a.profit >= b.profit"

[@ankitgarg3247]

@@divyasreedev6460 It worked..thanks a lot :)

[@divyasreedev6460]

@@ankitgarg3247 You're welcome

[@btRohit-st9jp]

@@divyasreedev6460 hey can you help me i am not getting the reason why ">=" not work if we have same profit which one come before don't matter na?

[@devilcoder6432]

@take U forward can you please explain nlogn solution for this problem

[@adityatiwari1022]

can we just sort it based on deadline (primary) and then sort it based on profit(secondary) That will just require linear time after sorting

[@asifd102]

thank you so much very good understanding

[@lord_yzal]

easy and concise explanation

[@lavanya_m01]

GOD LEVEL EXPLANATION!!!!

[@devanshmesson2777]

A Big Big THANKS for your contribution♥

[@gunashekarchenna3171]

Striver, you are the saviour!!!!

[@_-6912]

I understood the solution and intuition!

[@thelimit9719]

if profits aare same, we should not sort deadline by ascending order?

[@takeUforward]

Deadline wont matter since both of them will be having same profit and anyone after that will hace lesser profit.

[@tubanishat1139]

it took me 2 days to get a grasp on problem statement l

[@jitinroy2246]

if(result[j]==-1){ result[j]=arr[i].id; (replacing from result[j]=i; bcz in intuition part you said to store job id) count++; jobprofit+=arr[i].profit; break; }

[@adityamahimkar6138]

Bhai agar profits same ho toh phir id choose karneka kya? Just like we did in N meetings question or deadline like jiski deadline pehle voh pehle aise kuch ??

[@jinhuang7258]

Understood. Thank you!

[@husler7424]

Where is brute force i.e. DP approach!???

[@NavneetKumar-om1kc]

can anyone tell what is the base of log when we are discussing time complexity?

[@somyapratapsingh9849]

The way of solving question 💯

[@rudraprasaddash3809]

Sir, how are you editing GFG default code? For me, the main function is already there and I just have to write the function only, but I want to write the code from scratch.

[@ScienceSeekho]

Then write in your local code editor na bhai

[@lsrinivasamurthy]

Thanks bro for the nice and clear explanation.

[@sammohanty5507]

Hey brother All the best for the surgery.

[@Saikumar-kb4lf]

What surgery?

[@SatyaMantha]

Striver, you are awesome. Thanks a ton.

[@shubhamsood1406]

Time complexity is O(N^2) or O(N*logN) + O(N*M) ?

[@shashikantkumar5095]

Yeah i also thing, because there is one more loop inside to find the proper index

[@karthikpaladugula5424]

N logN is for sorting N*M is identifying the slot Why N^2 term??

[@akshitarora3524]

@@karthikpaladugula5424 if M=N-1(Worst Case) then complexity for identifying the slot will become N*(N-1) ~N^2

[@omkar.gaikwad]

max value of deadline (m) is 100, hence it will not be O(n*m)

[@MayankLC93]

@@omkar.gaikwad how?

[@aj9706]

Brilliant wat an explanation

[@yashpaste7700]

Thank you, striver!

[@bhaveshkumar6842]

Thank you so much!!!!!!!!!!!!

[@vaibhavsharma5923]

how to perform this sort?

[@kenadave]

Variables are "guys" 😄jokes apart, Thanks a lot for the content and really appreciate the hardwork 😇

[@binodbinod7537]

Thank you bhaiya!!❤️✨

[@pranabpaul6317]

Striver the comparison function need to be declared as static then it is running why so? please reply. i am also an condition if (jobCount == maxi) break; so that if jobcount is equal to maxi then no free slot is remaining so stop.

[@atharvgupta4218]

Can someone please tell me what is wrong in this code...Only 12 cases are passed class Solution { public: static bool comparator(Job a,Job b) { return (a.profit>b.profit); } //Function to find the maximum profit and the number of jobs done. vector JobScheduling(Job arr[], int n) { int maxDeadline=arr[0].dead; sort(arr,arr+n,comparator); for(int i=1;imaxDeadline) { maxDeadline=arr[i].dead; } } vectorv(maxDeadline+1,-1);int profit=0; int c=0; for(int i=0;i0;j--) { if(v[j]==-1) { profit+=arr[i].profit; v[j]=arr[i].id; c++; break; } } } vectorans; ans.push_back(c); ans.push_back(profit); return ans; } };

[@ajml_hnter]

C++ #include using namespace std; vector jobScheduling(vector &jobs){ sort(jobs.begin(), jobs.end(), [](vector& a, const vector& b) { return a[2] > b[2]; }); int cnt = 0, profit = 0, n = jobs.size(); vector take(n+1, false); for(auto &job : jobs){ for(int i=job[1] - 1; i>=0; i--){ if(!take[i]){ take[i] = true; cnt++; profit += job[2]; break; } } } return {cnt, profit}; }

[@satrap299792458]

What if each job takes more than 1 unit of time?

[@takeUforward]

Then from the back allocate that much time, simple!

[@thelimit9719]

"Each job takes 1 unit of time to complete" 0:25

[@devangrajarora7002]

​@@takeUforward I don't think that would work in the case where unit of time taken unit. For example, Job 1: Profit: 50, deadline: 5, time: 5 Job 2: Profit: 30, deadline: 5, time: 3 Job 3: Profit: 20, deadline: 5, time: 2 Now here we should perform Job 2 and Job 3 instead of just Job 1.

[@yatinarora1252]

@@devangrajarora7002 I think job 1 should be done as it is having maximum profit.Simply just we will be doing job1 for continous 5 days

[@manavshah7450]

Just fill that many slots which is equal to the job time. It will work. And about your example question. Job 1 will be selected and that is correct.

[@simrankureel94]

line 36 i will start from 1

[@pranjalpimpale8465]

where can I get the code?

[@yeswanthh5068]

Understood sir

[@RituSingh-ne1mk]

Understood!

[@lakshmiprasanna7058]

Understood 💯💯💯

[@rabatoaa857]

c++ 15:10

[@VikasGupta-ok9lh]

Understood

[@priyanshvatsal9791]

Understood 😇

[@shubhamraj5834]

Thanks sir

[@gautamsaxena4647]

understood bhaiya

[@abhishekanand9430]

thanks strivers

[@techtoys-tx9th]

Bhaiya please consider me back to the telegram channel , I also tried to contact to u through instagram , please bhaiya consider my request and I haven't spoke anything bad and abusive and negative through out the duration for which , I was a member of that telegram channel

[@takeUforward]

Telegram pe text kr do, ek hi text krna mentioning unban on telegram

[@deeksha6514]

On submitting this solution on gfg it's showing Runtime error for C++.

[@takeUforward]

They have changed the problem..

[@411_danishranjan9]

bhai ab try kar, ab submit ho jaayega

[@jitinroy2246]

understood

[@pravinthakur7791]

Needed a competitive coding partner with whom I can start my competitive coding journey .Anyone interested please reply?

[@_var.onwheels]

Yeah bro +1

[@ghoshdipan]

Like mind! Looking for the same.

[@koushikbiswas8289]

Can I??

[@cartube6219]

bhaiya foreign me koi nhi dekhta hoga apki video😭😭😭plz plz hindi me samjhya kijiye. and plz code in java as well in some of your video you use only cpp and you are famous for writing code in both languages. and truly logic samajh aaya ,, lekin code nhi

[@Ak-um1yg]

code kudse kar bhai . aur kon video dekhega iska tension mat le

[@jatinbhatoya8420]

public static int[] JobScheduling(Job arr[], int n) { int ans = 0; int count = 0; int doIt[] = new int[101]; Arrays.sort(arr, (a, b) -> Integer.compare(b.profit, a.profit)); for (int i = 0; i < arr.length; i++) { int j = arr[i].deadline; while (j > 0 && doIt[j] != 0) j--; if (j > 0) { count++; ans += arr[i].profit; doIt[j] = arr[i].deadline; } } return new int[]{count, ans}; }

[@pratikshadhole6694]

got it

[@shashankkumar1974]

hello sir can we sort the array with increasing order of deadline and if deadline is same then sort it according to max profit something like this. struct Job { int Deadline; int id; int profit; } static bool comp(Job j1,Job j2) { if(j1.deadline!=j2.deadline) return j1.profit>j2.profit; else return j1.deadline

[@kartikeyaagrawal5917]

it would have been right if the question said that the person doing the job cannot complete before the deadline .here in the question it is up to the person how he shedules his work. Say in ur case task 1(deadline 1day) has some profit "a" and task 2 (deadline 2) with profit "b" & task 3 with(deadline = 2) and profit c .Say here c>b>a in such a case ur program will choose task 3 and task 1 profit as a+c; but suppose he completes task 2 on day one and task 3 on day 2 he will ear b+c which is >a+c

[@manavshah7450]

Your comparator function is wrong. how can you return j1.deadline

[@aj9706]

Why fear when Java is here use lamda function

[@nisarggogate8952]

Here is a soln with sets. Making time complexity O(NlogN). The soon by TUF was of O(N^2) vector JobScheduling(Job arr[], int n) { sort(arr,arr+n,compare); set s; int ans = 0,i; for(i=1;i

[@takeUforward]

S.erase takes o(n), Refer www.cplusplus.com/reference/set/set/erase/

[@nisarggogate8952]

@@takeUforward ohhh I didn't know... Thank you for correcting me 🙏

[@arshad1679]

@@nisarggogate8952I think TUF is not correct. s.erase of a range is only O(n), else it is O(logn). Check the link.

[@MrShaundan]

@take U forward For the first version (erase(position)), amortized constant. For the second version (erase(val)), logarithmic in container size. For the last version (erase(first,last)), linear in the distance between first and last.

[@RaviSingh-qd5pz]

@@takeUforward I think erasing in set using an iterator take O(1) time so it has O(nlogn) time complexity.

[@jitenderyadav721]

Bhaiya voice phat rhi hai apki

[@parikshitrathore1510]

🔥🔥

[@yutaitadori7318]

cool 🆒 🔥🔥🔥🔥

[@saquelainmokhtar6016]

😍

[@SANDEEPKUMAR-zo5uc]

💘

[@takeUforward]

C++ Code Link: github.com/striver79/SDESheet/blob/main/jobSequencingCpp Java Code Link: github.com/striver79/SDESheet/blob/main/jobSequencingJava Live sessions on Insta: striver_79

[@songs-pu9bq]

🙌🙌🔥🔥

[@hritikchand9930]

bkl ka code python mein nhi chlta

[@pawanchoure1289]

😁

[@binodbinod7537]

😍😍😍

[@dhruvmahalwar8642]

what is problem with my code can someone explain vector JobScheduling(Job arr[], int n) { if(n==0) { return {0,0}; } else if(n==1) { return {1,arr[0].profit}; } int maxi=1; priority_queuepq; for(int i=0;i=1) { if(res[k]==-1||res[k]=1) { res[j-1]=res[j]; j--; } res[k]=profit; res[0]=-1; break; } k--; } } int count=0; int maxprofit=0; for(int i=1;i

[@sparshtaneja]

shoudn't it be slot[j] = arr[i].id;

[@naveensaicremsiyadlapalli3769]

slot[j]=arr[i].id

[@rahulgovindkumar3105]

Thank you bhaiya!!❤️✨

[@codingp110]

Understood!

[@NARUTOUZUMAKI-bk4nx]

Understood

[@abhinanda7049]

understood