L6. Job Sequencing Problem | Greedy Algorithm Playlist

[@adarshmv261]

Day 0 or Time 0 should not be considered... As per the prob in GFG !!!

[@roughero1353]

For the dsu approach imagine all deadlines as nodes of dsu which point to themselves. When a request for deadline comes in we fill the hash array deadline with the job id and and point the dsu deadline node to the previous day's deadline because current deadline jas become unavailable so we need the immediate previous empty deadline slot. Now if you simply do this the search will become logN so you need to do path compression so make the current requested deadline point to the ultimate parent deadline of previous day deadline. For example suppose day 3 is occupied and it points to day 2(day 2 is unoccupied as of now) and suppose request for day 4 comes in you make day 4 point to day 3 so when you next request for day 4 you can traverse back to day 2... with path compression you can directly make day 4 point to ultimate parent of day 3 which is day 2...

[@MANAVSAHNI-b2v]

Been looking for this everywhere... thanks a lot!

[@yathartharana7956]

Thanks :)

[@vamsikrishnagannamaneni912]

great explanation

[@priyadarsimishra7909]

There is a slight error in the code. The inner for loop should start from j = deadline (arr[I].dead) till j >= 1 not 0. Because otherwise we are adding arr[0] but there is no day 0 to do work

[@optimus_prime01]

ok

[@rudrakshtripathi4592]

On code360 by coding ninjas, 0 day is possible, so i thing it depends upon the question on the platform

[@adityaasthana8758]

Absolutely true...

[@vijeshsshetty]

beautiful

[@sumitmishra9795]

00:04 Solve job sequencing problem to maximize profit. 02:15 Maximize profit by scheduling jobs with deadlines efficiently 04:25 Maximize profit by scheduling jobs within deadlines. 06:21 Maximizing profit by scheduling jobs based on deadlines. 08:19 Job sequencing problem solved using Greedy Algorithm 10:09 Understanding the comparator logic and sorting based on profit in job sequencing problem 12:17 Iterating through jobs to maximize profit 14:17 Optimizing job sequencing problem complexity and space

[@samitkumar18]

String please 🙏

[@siddharthchaudhary2320]

Thank you striver for the yet another wonderful explanation. If anyone can tell how we can reduce the time complexity of internal loop to O(1) using DSU , please explain the logic. Thank you

[@shashanksinghal8395]

the question in greedy algorithm are very hard as compared to the arrays and linked lists. Does anyone else also feel that?

[@DevanshMatha]

yeah bro yesterday I encoutered a N meetings in one room problem in my OA and could't figure out the greedy approach , my brain could only think of DP.

[@rajputadi01]

yesss there are so many possibilities of being greedy i cant figure out which one is correct and in the end the solution turns out to be something completely different there is a new pattern in almost every question

[@NavyasriThalluri]

us

[@manansanghani1032]

ya even i feel that

[@animexworld6614]

Slightly mis typed Error in code It will be hash[ j ] = arr[i].jobid ... it will be hash of j not i

[@Dsa_kabaap]

Sir please start making videos on strings and stacks

[@shreyasrk6465]

if we consider the 0th index then it would be like having a deadline of 7 DAYS which is not true so we need to start from 1-6 that way we will be inside the deadline range👍👍

[@World-Of-Mr-Motivater]

striver ingeneral when speaking in an interview ,will you speak in 1.5x or 1 x speed?

[@achalsayee2534]

🤣😂

[@parthapratimhalder4888]

One thing I cannot understand why array of size 7 is taken where as max deadline is 6!!??

[@anubhav0355]

for a job with deadline 6, you will put it into hash[6] right? so size of hash must be 7 for it to have 6 as valid index!

[@Its_Shubham_Negi]

coz with size 6, the last idx would be 5 but we wanted 6, hence hash array of size 7 is taken

[@anshulsharma3137]

Hi Striver, we can even use priority queue to optimize, basically choose only the maximum profit job from the jobs with the same deadline.

[@dumpster-jackson]

That will add extra O(n) space -> priority queue. Hence sorting will be better

[@anshulsharma3137]

@@dumpster-jackson I have given the priority queue approach to further optimize the sorting solution from O(n*n) to O(n*logn) bro. Instead of using Dsu we can use priority queue to approach

[@dumpster-jackson]

@@anshulsharma3137 Good approach!!

[@masumali8356]

lovely explained...........

[@apmotivationakashparmar722]

Great Explaination.

[@stith_pragya]

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

[@UECAshutoshKumar]

Thank you

[@RajGupta-i3w]

Bhaiya, Strings aur Stack and Queue ki playlist kab laoge

[@kaichang8186]

understood, thanks for the great video

[@sougatadas3760]

Chin chan chu, ching lang ding lang du

[@kasiviswanath7981]

In the if condition thee is a small error we need to update hash[j] not the hah[i]

[@shashanksinghal8395]

why are you not counting the time complexity for calculating the max_deadline by looping through the array? that will add another O(N).

[@nandinii317]

as that will not make any significant difference to time complexity ..as TC is already approaching to N^2

[@shashanksinghal8395]

@@nandinii317 yes, that's correct, but he always calculate (almost) exact time complexity of each loop and then round it off. That's why I said that. Because in my approach I have same time complexity like him but with extra O(N).

[@prankishoriitkgp3772]

But Striver, what if all the deadlines are nth day; n=no of jobs In that case our time complexity would be O(n^2) but we are expected to solve in O(nlogn) time complexity Could you please clarify? can't we maintain a set data structure which will contain the days not occupied and according we will take the *(upper_bound(arr[i].dead)--) day

[@DeadPoolx1712]

UNDERSTOOD;

[@subee128]

Thanks

[@prathameshjadhav2942]

Understood

[@KartikeyTT]

tysm sir

[@nassimaamohammad]

greedy algorithm

[@adarshjaiswal7334]

What is the concept of day0? The day should start with 1 right?

[@divy04]

same doubt

[@priyadarsimishra7909]

I think it is to avoid like the deadline - 1 when changing value in hash, but the inner for loop should go from j = deadline to j >= 1 not till 0 because otherwise the output is not correct. I believe that is the error.

[@nitjsrstudent5423]

@@priyadarsimishra7909 yeah u r correct

[@EvilGod_10]

If we have no time to perform that job, so will neglect

[@valiz2628]

❤

[@Professor-du2pf]

cout

[@viveknandan4950]

you forget to put ;

[@iamnottech8918]

@@viveknandan4950 you forget to put------is not recoznized------compile error .

[@Shimu-x8r]

can you please change the song that you have added at the end of each video.....

[@anuragmandal3136]

really cant understand anything he says

[@adarshjaiswal7334]

You definetly will, Just don't quit for next 22 days!!

[@iamnottech8918]

u need to stop video multiple times in between and think why he said that if video is of 16 min it means it can take atleast 1hr to understand it is normal.

[@noobnessmee]

get your fundamentals right

[@kushalsinha6917]

skill issue

[@vanshikasoni6950]

Have you seen his previous videos? Because with background knowledge you will not be able to get it... Trust me with a sound background knowledge you can understand it all.... This guy is 10/10 on ur when it comes to DSA in C++

[@Carson00_11]

Hello baby 🤗

[@lofi_feels1924]

💀💀

[@avisoft-l2p]

hash[j]=arr[i].profit

[@KedarBhawthankar]

chin tapak dam dam

[@aryankumar3018]

Understood