Weighted Interval Scheduling Python Code

Key Takeaways

in this video we want to implement an algorithm in Python on how to solve the weighted interval scheduling problem so I've written some skeleton code and the the function previous intervals will find the P vector which we saw in the last video find solution is used for backtracking to find the optimal jobs compute opt is to apply the recursive formula which we also saw in the last video the way the interval is to find the optimal for each of the subproblems so this is for a specific subset J and here we will run run this one for each of the four for J equals 1 to up to n and so let me just copy in this so I've written out all the all of the jobs which we saw also in the last video the they are the same and also opt for which will we will store all of the optimal solution to all of the subproblems eventually to including all of the jobs where we have n jobs in this case we have 8 + o to store all of the best I guess best jobs to pick so what we want to do first is that we want to sort it by by finished time and finish time is of second element well let's see we will have I to be a list of all of those tuples and we want to sort I when to sort I by the second element so we can use the key so we use the anomalous function lambda and we have the key for each that is a tuple and we want to sort it by the first I mean the this the second element which is first index now that we have it sorted by finish time we want to find the P the p-vector and i think this is the most tricky to find so maybe it's a good thing that we start with this function what we're going to do is we're going to first define P is an empty list we're going to say start to be the list of all of the starting times which is just ask zero for tasks in AI and then the finish which is tasks of one for tasks in AI and the thing we're going to utilize is that we know that this list is sorted right this might not be sorted but we at least know this is sorted because we sorted before we send it into this function then we want to or I in range of Len of I so we want to go through each of art of the jobs and then what we're going to use to make it and so this will make it I'm Quebec City n so for each we have to find an algorithm to find it in log n time and what we can use here is a variant of binary search I guess bisection search so how this function will work and let's our dysfunctional is that let's say we have a list of Finnish times which are sorted so 10 20 30 for example then we have a starting time of let's say 15 so what we know is that this finish time is greater than this one right which means that they overlap but this one finish time is less than or equal to the starting time so we want to have this one right what the bisection method you does is that it will it will first take as input the list which is sorted and it will take an element and it will find where to insert this element so that this list is still sorted right if we insert 15 into the first index here in between 10 and 20 then this will still be sorted and what we want to know is which of all of these elements so what is the index of these of the element where the finish time is less than the starting time so in this case it's 10 right so we can just use this but then subtract 1 and this will be the index so for example if the starting time would be 25 then we know that well this is greater than 25 means at the overlap 20 is less than or equal to 25 which means that they don't overlap and I mean 10 is also less than 25 but we want the greatest index so we want this one which is index 1 so let's say we do the same but we we have start you start which is 25 we will get the first index okay so we just do this index is bisect dot bisect finish come a start of I and then we subtract 1 to get that index and then we just append it right so if it's if it's if it's the zero element if it's the first one so I mean if there are no element then it will be minus one and that's one thing we will have to keep in mind when we do the the the rest of the functions since Python is zero indexed this will be a little bit different from the the video where we went through the algorithm where everything was 1 indexed so a little bit confusing perhaps then we just return P so here we can print P for example - 1 - 1 0 which is contrasted to what we found in the last video this was 0 0 0 1 but that's just because it's 0 indexed so the next thing is that we want to you we want to implement this function which is to apply the recursive formula and so what we want to do if J the base case if J is minus 1 remember zero index so it will be minus 1 instead of 0 at this time then we just return 0 else what we want to do is that we want to return the max of AI of j2 plus compute up of pfj or the compute opt of J minus one right one thing that I believe I'm missing in the last video but we want to do also is that if we already have this value pre-computer we don't want to compute it again so we can do an else--if statement here if zero is if J is very equal to zero and Jays lesson the length of opt which means that essentially we have that one stored right then we can return that instantly right we don't have to come to do this cursive ly all over again if we already have that value computed so this is just to to reuse the item and the the opt values that we've already computed the for then in the wit interval we want to forge a in range of Leno aye I want to go through each of them and then we want to compute opt of J right so it will start from 0 1 etc and then we want to append this to opt okay so we now can print up I guess and so this will just run this for each of the subproblems and then it will have the opt vector which we saw in the last video as well so we have yeah three three four four and then eight for the last three which is exactly the same so it seems to be correct but I guess we want to return opt here but we want to just return to the last one right because this is the optimal total weight for all of the items let's see what is left so what is left is that we want to also find I mean this is great right we have optimal solution which is great eight but we also want to know which items did we we I mean which jobs who did we take so I guess in this case it's easy we can just see that well I know it's this one and I think this one but even for this small case it's a little bit confusing so we want to make a function that can find those using backtracking and similarly here we can write if J is one if my J is minus one then we just return this is the base case and then otherwise we check if if the wait so this is I have J of to write this you just essentially copy this if this where we took that item J is greater equal to opt of J minus one that means that taking the item is at least as good as not taking it or better right then we add this to our to our list of best jobs to pick and we add that jate one and then we call this function again but we now want to have only the intervals that don't overlap with the one we took or if this is not the case then this means that well we want to find the optimal for this regarding item J so then we just want to run it again on J minus one okay so for example in this one here we want to run find solution on on let's see what is if I want to run down find solution the length of I minus one since remember we have it's zero index we just subtract one and then we will have all of the a best jobs to pick in Oh since we have added those in the backtracking so now we can we can print the maximum weight is optimal solution and we also have the best items to pick I keep saying items I mean jobs the best jobs to to take take are the Oh list and the the only thing here is that since we start from the last one and we move our way backwards the items will be in their reverse order so we can right here just revert the order of the list so in this case the maximum weight is 8 oh wait this is not great mmm approximately 10 hours later found the problem right here when we see here when we find the solution we don't want to actually compute it again yes and that causes a problem not really sure why that would cause a problem though but we want to have opted here like this and this adds the job a little bit confusing because I feel if we're just one computer opt on pfj that would still return up to J I mean up tothe pfj for some reason it doesn't and I'm gonna have to think a little bit about about that white actually doesn't either way this should be upped of P of J right because we already have the values computed and so we don't want to run it again and yeah so this is the weighted interval scheduling problem hopefully I'll figure out a solution for why that works and the other one didn't and I mean if you have a an answer for that please comment in the below okay so thanks for watching this video and I hope to see in the in the next one