I like this kind of a visualization. This is akin to the 2D matrix that we draw, except, here we show both the indices on the same axis instead of making a matrix, and instead of writing values to A[i,j], we simply overwrite A[i]. This problem is again similar to the maximum increasing subsequence problem where we consider all subsequences (combination of i&j) and keep updating the values all the way till the end.
I think it's possible to make this quite better. Whenever you move "i" to the next item, you don't have to push "j" back to the first item and compare all of them. Instead, you would check if job at "j" overlapped with "j-1", if they didn't, then the sum of both would be the max profit for current's "j". If they did, then you check "j" against "j-2" and so on until you find a job which didn't overlap with "j", them the sum of them would be max profit for current "j". That wouldn't change the time complexity because the worst case would be the same, but for better scenarios it'd reduce the amount of iterations.
Another thing that would reduce the number of iterations would be to use your technique the first time a job overlaps with the job at "i". Instead of incrementing "j" and checking for overlaps again. This is because the jobs have already been sorted by finish time. So the first time the job at "i" and job at "j" overlap, reset "j" to 0 or follow your technique.
this can be done in the same way but with lesser calculations - thats what dp is. you need to assign j to the last possible job that is compatible with i, and use the value in the array at jth position as we already calculated the max value for that position so we just need to take that and dont need to iterate over the entire array (j=0 to j
In the example used here, the array holds [5 6 10 14 17 16] so if another job is there with a start time 10 then u will take the value 16 as its ending time is 9 and is non overlapping but the true answer should be 17 with ending time 8 . So that's why it contradicts ur approach. Plz clarify me if I am wrong.
Always draw the brute force solution tree, then without any issue you can see duplicate nodes and then start at the leafs and cache results. That's pretty much every dynamic programming issue.
Awesome...I was thinking of include and exclude strategy but this is much better...This is the same strategy as finding Longest Increasing Subsequence ...only fact that instead of comparing values we are comparing and including only if not overlap
Your explanations are amazing. Thank you for providing java code link for each algorithm. It is the best way to understand implementation of algorithm.
Please explain one thing to me. In certain problems you use 2D arrays and in certain problems you use 1D arrays. Also the operations you choose to do in these arrays sometimes differ vastly. Please tell how you choose the array size and how do you determine the operations to be done in the array. I understand the solution, but I just cannot find any common pattern between all your dynamic problem solutions. It seems like you engineer an elegant solution for each and every case. If you have a secret technique, please share with us less intelligent people.
This is akin to the 2D matrix that we draw, except, here we show both the indices on the same axis (instead of making a matrix and showing two axes), and, instead of writing values to A[i,j] (as in matrix), we simply keep updating A[i]. This problem is again similar to the maximum increasing subsequence problem where we consider all subsequences (combination of i&j) and keep updating the values all the way till the end. View i and j on two axes (row and column), and you'll get the same answer.
i dont think the algorithm is correct, for T[j] + profit[i] how do you make sure T[j] does not include intervals that is not compatible with interval i even though interval i, j are compatible ?
@@prayagbhatt122 other teacher and sir also provide good quality without donation man.... I think you are new to using you tube for learning so please explore yourself and then tell others..!!!!
Hello +TusharRoy2525 first of all big thanks for all the awesome video... its DP made easy :) I have a question: There two approaches which we take based on a particular question: Scenario 1(Longest Palindromic sub-sequence or Optimal BST) : we create 2D matrix and use bottom up approach i.e. we consider Length=1,2 ... and so on. In other words, we see what if there is only one element and the what if there are two elements then 3 elements and so on..... to reach to the final solution. Scenario 2(This Problem or longest increasing sub-sequence) : We create 1D array and at any particular element we update its value so that we know what is the answer till now and this way we have our solution for ith sub-problem the ith position. How do you identify which approach to take and when? Unfortunately I find both case to be very very similar. For example, when I started to solve this problem by myself I was going like what if I have only one job and tried making 2D matrix and use only upper half as we did it for Scenario 1 like problem. Another question is, in Optimal BST like problem we consider combinations(lets say for two element i.e. L=2) {(1,2), (2,3), (3,4)} not (1,3) or (1,4) why is that?
Hi Tushar, in your dp solution on github the code is somewhat incorrect as for the example you have provided on github the answer should 23 whereas you solution gives 17. Can you please check i think you are missing one job int the solution. I think you are missing the equal sign in " if ( job[j].end
I can see some questions whether we can sort it based on start time. Yes, we can sort with start time in non increasing order. In this problem, we go with a greedy approach where we want to place more number of jobs. So, if we try to push the start time to right, there is a chance to place more number of jobs before that particular job is done. Also, if we try to push the end time to left, we can place more jobs to the right. We always try to select the job which disturbs minimum number of jobs.
Tushar, thank you very for all these videos. I have one question: Is there any way to know when to use arrays and when to use cost matrix? When I watch your videos I understand the problem solving process. But I cant figure it out on my own. Thanks in advance. Best regards from Serbia :)
I believe its about intuition and how well you can relate one problem to another. A simple example would be, any problem where we have to find "max profit", you must try thinking how well it would perform with DP and so on..
guys he just gives the DP solutions. So, the answer to your question is in "Geeksforgeeks", where they explain when to use dp and how should we approach solution using DP for each problem. Whereas Tushar Roy explains the solution part.
First one ends at 6 and the second job starts at 6 so they don't really overlap. Think of it like the school's classes. First class's timing is from 9:00 to 10:00 and the second class's timing is from 10:00 to 11:00. So, they don't really overlap but the second class starts right when the first job finishes.
no because in kadane we have to be continous while in this case u dont need to consider continous jobs. it is a variation of longest increasing subsequence poblem.
Hi Tushar, your code runs in O(n*n) in worst case,while we can reduce it to nlogn , by finding last job which finish before or at the same time of given job start time using binary search...
Suppose the next job is(start=10,end=11,profit=1). Then if you used Binary Search just to find the last non-conflicting job ID, you'll end up with a profit of (16 + 1) instead of (17 +1). This renders that solution incorrect. This is the kind of issue I have with all of the nlogn solutions i've found and it hasn't been explained to me in a way that reconciles that issue.
unless perhaps youre just using it to find the split point. and then iterating j = 0 to that last found non-conflict.... in which case worst case is still n^2
Since the intervals are already sorted by their finishing time, the profits before i should be in non-decreasing order. No need to iterate after binary search.
Not really along the lines of LIS, but surely the complexity can be reduced, with tradeoff overhead on the space. Here is the idea: Maintain a SegmentTree, which can answer the max. until an ending point. Assume a fat array with an index representing the ending time since inception, and the value at the index as the maximum value that can be retrieved till that ending time. Build a segment tree on top of this. When at index idx, in the original approach of the video, denoting the time-range to be : [st, en], ask the Segment tree for the maximum value in the range [0, st], the retrieved value + value at the current index is one of the answers for ending time -en-, now update your segment tree if the need be. Overall complexity: O(nlogn), with extra space: O(max_end_time)
better and more optimalsolution you can follow is here : www.geeksforgeeks.org/weighted-job-scheduling-log-n-time/ and for selected jobs just maintain prev pointers in a separate array which you can traverse
@@jerrygu1 I think that would take n-1 arrays because you wouldn't know what's the max profit until you reach the end of the array, so you might have to keep those n-1 arrays till the end. How about traversing non overlapping jobs to the left from the index of maximum profit in the array? this could be done in linear time
***** Yes but I think I correctly understand that if you have missed that part then you need to search for max at the end manually instead of returning the last element . Right? Anyways awesome job
No, Becuase we are checking jobs before the current job on the left.................But, if we would check jobs on the right of the current job, then we would be sorting it by start time. I hope you understand.
yeah..the one given in github looks for a correct pair of jobs(non-overlapping) and then breaks,which is not the case in video..it continues to update the current profit
umm I meant t[1] = profit[1]; that is because you can do one and only one job when there is no other jobs to compare, so that is the base case for this recurrent formula.
But when he is executing the algorithm he took the maximum between the calculated value, with previous values, and the atual value (here is the necessity to initialize all values, and not only the first one). But I cannot find a justification for this by myself.
No we have to sort by ending time and not the starting time.. if you sort by starting time in the ascending order..you'll be stuck with a job with minimal profit and doesn't even end soon.. like startingtime = 1 and endTime = 100 with a profit of 5.. We don't wanna run that.. so if we at least sort it by ending time in ascending.. we will be left with jobs which complete sooner.. minimal risk.
thanks for the reply it take such a long time to response i even had forgot why i had asked this question but thanks a lot tuncating bro iam very much grateful of you
How'd you approach the same problem if we also needed to output the sequence in which we did the jobs? like Job2-->Job3-->Job5.. like that.. instead of the profit alone?
Hi tushar, thanks for your videos. I have a one problem that i cant solve with DP. First of all sorry for my bad english. Given N that represents books page number. So how many digits were used to number all that books page .1 to N we should find every digits quantity, like 0 is 10 1 is 11 2 is 12 3 is 4 etc. hope you will reply me,ty :D
+Tushar Roy thank you for reply , if you know n (log n ) video? i want to know how to solve O(n log n) time really thank you for video have a nice day~
I like this kind of a visualization. This is akin to the 2D matrix that we draw, except, here we show both the indices on the same axis instead of making a matrix, and instead of writing values to A[i,j], we simply overwrite A[i]. This problem is again similar to the maximum increasing subsequence problem where we consider all subsequences (combination of i&j) and keep updating the values all the way till the end.
Not that it changes the running time, but once you hit an item that overlaps, you can increase i and reset j to 0, since you've sorted by finish time.
You’re an actual lifesaver
I think it's possible to make this quite better. Whenever you move "i" to the next item, you don't have to push "j" back to the first item and compare all of them. Instead, you would check if job at "j" overlapped with "j-1", if they didn't, then the sum of both would be the max profit for current's "j". If they did, then you check "j" against "j-2" and so on until you find a job which didn't overlap with "j", them the sum of them would be max profit for current "j".
That wouldn't change the time complexity because the worst case would be the same, but for better scenarios it'd reduce the amount of iterations.
what if input is intervals = [[1,2],[3,5],[4,6],[7,9]] , weights = [1,10,1,1]
Another thing that would reduce the number of iterations would be to use your technique the first time a job overlaps with the job at "i". Instead of incrementing "j" and checking for overlaps again. This is because the jobs have already been sorted by finish time. So the first time the job at "i" and job at "j" overlap, reset "j" to 0 or follow your technique.
Thanks a lot Tushar for taking your time out and making these videos.They are very useful.
this can be done in the same way but with lesser calculations - thats what dp is. you need to assign j to the last possible job that is compatible with i, and use the value in the array at jth position as we already calculated the max value for that position so we just need to take that and dont need to iterate over the entire array (j=0 to j
In the example used here, the array holds [5 6 10 14 17 16] so if another job is there with a start time 10 then u will take the value 16 as its ending time is 9 and is non overlapping but the true answer should be 17 with ending time 8 . So that's why it contradicts ur approach. Plz clarify me if I am wrong.
king of dynamic programming
Always draw the brute force solution tree, then without any issue you can see duplicate nodes and then start at the leafs and cache results. That's pretty much every dynamic programming issue.
Yeah this solution jumped straight into the optimal without any intuition of why. Bad explanation in my opinion.
Awesome...I was thinking of include and exclude strategy but this is much better...This is the same strategy as finding Longest Increasing Subsequence ...only fact that instead of comparing values we are comparing and including only if not overlap
Your explanations are amazing. Thank you for providing java code link for each algorithm. It is the best way to understand implementation of algorithm.
Most clear explanation for me!
Great effort sir but it won't work in o(nlog(n))... pls try to make a video on it
Here comes the solution of homework. Sweeeeeet~~!
You made me confuse man it may be that you saying correct but explanation needs more info
your explanation is good, but the bellman equation you wrote is wrong and in real thats not how compute the optimal solution is calculated
Thank you for providing detailed video.
Think of each job as an weighed edge, and connect them into a longest( shortest ) path problem.
Yeah u are right.
thank you my friend sending lots of love from tanzania dar es salaam
your video is so useful, thank for sharing us free
great work, I have a doubt while adding j to i don't we need to check j doesn't overlap with j - 1? please suggest
Please explain one thing to me.
In certain problems you use 2D arrays and in certain problems you use 1D arrays. Also the operations you choose to do in these arrays sometimes differ vastly.
Please tell how you choose the array size and how do you determine the operations to be done in the array.
I understand the solution, but I just cannot find any common pattern between all your dynamic problem solutions. It seems like you engineer an elegant solution for each and every case. If you have a secret technique, please share with us less intelligent people.
Exactly !
This is akin to the 2D matrix that we draw, except, here we show both the indices on the same axis (instead of making a matrix and showing two axes), and, instead of writing values to A[i,j] (as in matrix), we simply keep updating A[i]. This problem is again similar to the maximum increasing subsequence problem where we consider all subsequences (combination of i&j) and keep updating the values all the way till the end.
View i and j on two axes (row and column), and you'll get the same answer.
You can use binary search to optimize the solution to O(nlogn)
Great explanation, thank you!
Somehow binary search can be incorporated to make this faster...
This has time complexity of O(n^2) and it doesn't work for all test cases of leetcode 1235 problem.
i dont think the algorithm is correct, for T[j] + profit[i] how do you make sure T[j] does not include intervals that is not compatible with interval i even though interval i, j are compatible ?
Because the end time is sorted in ascending order buddy.
super helpful video. Thanks soo much. However, is a there a faster algorithm for this?
Sir one suggestion is improve quality of video...
But your teaching method id very impressive
Accha , Free me padhata he wo dekh na , Warna Donation de Use.
@@prayagbhatt122 other teacher and sir also provide good quality without donation man....
I think you are new to using you tube for learning
so please explore yourself and then tell others..!!!!
@@sohammehta8815
I think you are new on TH-cam , Every is making video for money and some are not provide All content without money.
@@prayagbhatt122 I don't want to talk with those who do not know about the thing and just take place and tell bla bla bla....
Hello +TusharRoy2525
first of all big thanks for all the awesome video... its DP made easy :)
I have a question:
There two approaches which we take based on a particular question:
Scenario 1(Longest Palindromic sub-sequence or Optimal BST) : we create 2D matrix and use bottom up approach i.e. we consider Length=1,2 ... and so on. In other words, we see what if there is only one element and the what if there are two elements then 3 elements and so on..... to reach to the final solution.
Scenario 2(This Problem or longest increasing sub-sequence) : We create 1D array and at any particular element we update its value so that we know what is the answer till now and this way we have our solution for ith sub-problem the ith position.
How do you identify which approach to take and when?
Unfortunately I find both case to be very very similar. For example, when I started to solve this problem by myself I was going like what if I have only one job and tried making 2D matrix and use only upper half as we did it for Scenario 1 like problem.
Another question is, in Optimal BST like problem we consider combinations(lets say for two element i.e. L=2) {(1,2), (2,3), (3,4)} not (1,3) or (1,4) why is that?
What's your question?!
Click 'Read More' you'll see it .. xD
This problem is quite analogous to longest increasing sub sequence
maximum increasing sum subsequence
Hi Tushar, in your dp solution on github the code is somewhat incorrect as for the example you have provided on github the answer should 23 whereas you solution gives 17. Can you please check i think you are missing one job int the solution.
I think you are missing the equal sign in " if ( job[j].end
Nice but this approach gives TLE... it can be done in nlong use binary search instead of linear search after the initial sort.
I think the final answer is wrong, it should have been 17.
You are amazing.
I can see some questions whether we can sort it based on start time. Yes, we can sort with start time in non increasing order. In this problem, we go with a greedy approach where we want to place more number of jobs. So, if we try to push the start time to right, there is a chance to place more number of jobs before that particular job is done. Also, if we try to push the end time to left, we can place more jobs to the right. We always try to select the job which disturbs minimum number of jobs.
time complexity will be n^2
Tushar, thank you very for all these videos. I have one question: Is there any way to know when to use arrays and when to use cost matrix? When I watch your videos I understand the problem solving process. But I cant figure it out on my own. Thanks in advance. Best regards from Serbia :)
+Nemanja Stankovic I would also like to know how to get that insight of what to use and when to use it!
I believe its about intuition and how well you can relate one problem to another. A simple example would be, any problem where we have to find "max profit", you must try thinking how well it would perform with DP and so on..
guys he just gives the DP solutions. So, the answer to your question is in "Geeksforgeeks", where they explain when to use dp and how should we approach solution using DP for each problem. Whereas Tushar Roy explains the solution part.
why are we sorting according to end time
so the time complexity is O(n^2)
i don't think sorting part was necessary
Bro (4,6) (6,7) overlapp at 6 , both job is present at 6th sec.
First one ends at 6 and the second job starts at 6 so they don't really overlap. Think of it like the school's classes. First class's timing is from 9:00 to 10:00 and the second class's timing is from 10:00 to 11:00. So, they don't really overlap but the second class starts right when the first job finishes.
nice work again
My question:is this approach same as kadane's algorithm?
no because in kadane we have to be continous while in this case u dont need to consider continous jobs. it is a variation of longest increasing subsequence poblem.
Tushar thanks a lot, your explanation is concise to the point and well articulated.
can you explain how to print selected job please?
can you pls post a video of binomial coefficients dynamic programming
Hi Tushar, your code runs in O(n*n) in worst case,while we can reduce it to nlogn , by finding last job which finish before or at the same time of given job start time using binary search...
Hmm, but even we find the entry, we still need to iterate all items before the split point to find the max weight value?
But what if there is a point before that where you get max profit?
Suppose the next job is(start=10,end=11,profit=1). Then if you used Binary Search just to find the last non-conflicting job ID, you'll end up with a profit of (16 + 1) instead of (17 +1). This renders that solution incorrect. This is the kind of issue I have with all of the nlogn solutions i've found and it hasn't been explained to me in a way that reconciles that issue.
unless perhaps youre just using it to find the split point. and then iterating j = 0 to that last found non-conflict.... in which case worst case is still n^2
Since the intervals are already sorted by their finishing time, the profits before i should be in non-decreasing order. No need to iterate after binary search.
can you past a video for task scheduling problem
can we reduce time complexity of this using LIS technique to O(nlogn)
Not really along the lines of LIS, but surely the complexity can be reduced, with tradeoff overhead on the space.
Here is the idea: Maintain a SegmentTree, which can answer the max. until an ending point. Assume a fat array with an index representing the ending time since inception, and the value at the index as the maximum value that can be retrieved till that ending time. Build a segment tree on top of this.
When at index idx, in the original approach of the video, denoting the time-range to be : [st, en], ask the Segment tree for the maximum value in the range [0, st], the retrieved value + value at the current index is one of the answers for ending time -en-, now update your segment tree if the need be.
Overall complexity: O(nlogn), with extra space: O(max_end_time)
how to output the selected jobs?
github.com/tuncatunc/weighted-job-scheduling
Keep a track of the prev job from which the last update(max) happened.
Maybe you have c++ project ?
better and more optimalsolution you can follow is here : www.geeksforgeeks.org/weighted-job-scheduling-log-n-time/ and for selected jobs just maintain prev pointers in a separate array which you can traverse
What if after we finished finding the max value we wanted to find the jobs that make up this value?
+Connor Lewis just backtrack from the max value to get the jobs selected
Could you elaborate a little if you can please?
I love the way you prounnce array 😂😂
And I love the way you spelled pronounce
Can anybody help me? I want to print out the jobs selected as well!
make an array that stores the previous selected job
@@jerrygu1 I think that would take n-1 arrays because you wouldn't know what's the max profit until you reach the end of the array, so you might have to keep those n-1 arrays till the end. How about traversing non overlapping jobs to the left from the index of maximum profit in the array? this could be done in linear time
How to keep track of the jobs which are selected?
what if the end point of jobs are same, what will we do during sorting?
Best video I found! Thank you very much! You made it look very simple.
Why sort by end time instead of start?
From the github link line 90 91
for(int i=1; i < jobs.length; i++){
T[i] = Math.max(jobs[i].profit, T[i-1]);
You have missed this part I guess
***** Yes but I think I correctly understand that if you have missed that part then you need to search for max at the end manually instead of returning the last element . Right? Anyways awesome job
***** Thankyou
Had anyone spotted the pink gal? 🤨
Isn't this in O(n^2) runtime?
Hi Tusar
Dose sorting using the start time can be also used for this algorithm.?
No, Becuase we are checking jobs before the current job on the left.................But, if we would check jobs on the right of the current job, then we would be sorting it by start time. I hope you understand.
hello Tushar ' what is the running time?
What is the worst case running time for weighted job schedulling dynamic programming ?
This method runs in O(n^2)..but by using binary search we can reduce it to O(nlogn)
Beware! Code given at the description github link runs a different algorithm than what he is explaining.
yeah..the one given in github looks for a correct pair of jobs(non-overlapping) and then breaks,which is not the case in video..it continues to update the current profit
How can I express this via a recurrence formula? You did not show us the base case...
Lucas Kanashiro base case is T[i] = profit[i], you just gotta compare it with the new value tho
And do you have any justification for this?
umm I meant t[1] = profit[1]; that is because you can do one and only one job when there is no other jobs to compare, so that is the base case for this recurrent formula.
But when he is executing the algorithm he took the maximum between the calculated value, with previous values, and the atual value (here is the necessity to initialize all values, and not only the first one). But I cannot find a justification for this by myself.
Thanks man.
Why sorting
Dont we have to sort the jobs array in order of their starting day.
for example: if I take jobs array to be
{7,8} .......{2,6}
No we have to sort by ending time and not the starting time.. if you sort by starting time in the ascending order..you'll be stuck with a job with minimal profit and doesn't even end soon.. like startingtime = 1 and endTime = 100 with a profit of 5.. We don't wanna run that.. so if we at least sort it by ending time in ascending.. we will be left with jobs which complete sooner.. minimal risk.
@@GokulRG sorting by start or end time both will work.
whats meant by overlap how to find out the overlap jobs
interval of a jobs is defined by [start, finish]. Suppose two jobs with intervals [s1, f1] and [s2, f2]. Two jobs overlap if s2 < f1
thanks for the reply it take such a long time to response i even had forgot why i had asked this question but thanks a lot tuncating bro iam very much grateful of you
super
Thank you so much
what is the time complexity of this algorithm?
O(n^2)
Beautiful explanation thank you sir.
you seem distracted bro
i can't understand bro.................
Hey bro will u please let me know what are you doing now .....
As I want to predict my future
As I also couldn't understand
flow shop nd job shop r same??
How'd you approach the same problem if we also needed to output the sequence in which we did the jobs?
like Job2-->Job3-->Job5.. like that.. instead of the profit alone?
Hi tushar, thanks for your videos. I have a one problem that i cant solve with DP. First of all sorry for my bad english.
Given N that represents books page number. So how many digits were used to number all that books page .1 to N
we should find every digits quantity, like
0 is 10
1 is 11
2 is 12
3 is 4 etc. hope you will reply me,ty :D
Are you waiting to this day :)
thanks
thanks a lot
gr8
√2 x 10^5 views, nice
hi Tushar Roy,
thank you for you video,
i have a question.
in this problem(weighted interval scheduling) time complexity
O(n *long n) is best?
+Tushar Roy thank you for reply ,
if you know n (log n ) video?
i want to know how to solve O(n log n) time
really thank you for video have a nice day~
Complete code: goo.gl/yi489b
speak indonesian pls i dont understand
this is too slow :(