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
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...
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
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
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.
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
@@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
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👍👍
@@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).
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
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.
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.
![Good Book about Low-Level C++ [from a quant dev]](http://i.ytimg.com/vi/lVwAJSGs2ds/mqdefault.jpg)
Day 0 or Time 0 should not be considered... As per the prob in GFG !!!
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
ok
On code360 by coding ninjas, 0 day is possible, so i thing it depends upon the question on the platform
Absolutely true...
beautiful
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...
Been looking for this everywhere... thanks a lot!
Thanks :)
great explanation
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
String please 🙏
Sir please start making videos on strings and stacks
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
Slightly mis typed Error in code It will be hash[ j ] = arr[i].jobid ... it will be hash of j not i
the question in greedy algorithm are very hard as compared to the arrays and linked lists. Does anyone else also feel that?
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.
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
us
Hi Striver, we can even use priority queue to optimize, basically choose only the maximum profit job from the jobs with the same deadline.
That will add extra O(n) space -> priority queue. Hence sorting will be better
@@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
@@anshulsharma3137 Good approach!!
striver ingeneral when speaking in an interview ,will you speak in 1.5x or 1 x speed?
🤣😂
One thing I cannot understand why array of size 7 is taken where as max deadline is 6!!??
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!
coz with size 6, the last idx would be 5 but we wanted 6, hence hash array of size 7 is taken
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👍👍
UNDERSTOOD......Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Great Explaination.
lovely explained...........
understood, thanks for the great video
Bhaiya, Strings aur Stack and Queue ki playlist kab laoge
Thank you
why are you not counting the time complexity for calculating the max_deadline by looping through the array? that will add another O(N).
as that will not make any significant difference to time complexity ..as TC is already approaching to N^2
@@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).
In the if condition thee is a small error
we need to update hash[j] not the hah[i]
UNDERSTOOD;
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
What is the concept of day0? The day should start with 1 right?
same doubt
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.
@@priyadarsimishra7909 yeah u r correct
If we have no time to perform that job, so will neglect
Thanks
Understood
tysm sir
greedy algorithm
❤
cout
you forget to put ;
@@viveknandan4950 you forget to put------is not recoznized------compile error .
can you please change the song that you have added at the end of each video.....
really cant understand anything he says
You definetly will, Just don't quit for next 22 days!!
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.
get your fundamentals right
skill issue
Hello baby 🤗
💀💀
hash[j]=arr[i].profit
chin tapak dam dam
Understood