Weighted Interval Scheduling Algorithm Explained

Key Takeaways

hi and welcome in this video I want to go through how to solve the weighted interval scheduling problem with a dynamic programming approach and in the next video I will implement an algorithm in Python so the problem description is that we're given a list of jobs which all have a sorting finish and a profit or weight associated with it and the goal is that we want to find the subset of these jobs with the maximum weight maximum total weight where each job is disjoint which means that the jobs cannot occur at the same time the notation we'll use is they for a job I we have a starting time finish time and a weight very very quick and simple example we consider three jobs but if we consider taking the first job that means that we cannot pick job to because they overlap and if we pick job one then we can still pick job three so a total total weight will be two or we consider taking job two for a total weight of three but then we cannot pick job one or job three so in this case we take the second job for a total weight of three which is greater than two so if we're going to solve this problem using dynamic programming and idea is that we assume that we only look at the last job so the last job meaning we have sorted the jobs by finish time and we look at the last job with the latest finishing time then either we pick that job or we don't so that sounds simple let's examine it in a little bit more detail in case one that we pick it well then we need to remove all overlapping jobs and we need to compute a solution for the subproblem of the jobs left in case two we don't pick it well then we compute the optimal solution for the subproblem with n minus 1 items left so it becomes easy to see that if we have solved the subproblems then we can easily just examine the two choices well pick it or don't pick it but that assumes that we have solved the subproblems so this suggests a dynamic programming approach we can solve that we can solve it by recursively looking for J equals 1 2 up to n for the subproblems and we can define op J to be maximum weight that can be achieved by selecting the jobs from the first J intervals and we need to define a help function that is useful for removing overlapping intervals but we let P of J be the largest index I such that F of I is less than equal to s of J so what this means is that if the finish time is less than equal to the starting time of job J that means that they don't overlap right if the finish time for something is greater than the starting time that means that they overlap so since we have sorted by we have sorted by finish time if we take the largest index that means that we will get the job job I that is closest to job J so this jar this function is useful to remove overlapping jobs but let us understand this function a little bit better with an example so consider if we look at job one and there are no previous jobs so P of 1 is just 0 looking at job 2 then we notice here that the finish time of job 1 is a greater than the starting time of job 2 which means that they overlap and P of 2 is also 0 for job 3 we notice also that the finish time of both job 1 and job 2 is greater than starting time of job 3 so P of 3 is also 0 and now considering job for we see that well the finish time I mean it overlaps with job 2 and job 3 but it doesn't overlap with job 1 so if P of 4 is equal to 1 and for the last one or let's just look at one more because I think you get the idea so for job 5 we noticed that well it overlaps with job for and job 3 but not the job - or job 1 so we remember that we take the largest index and since 2 is greater than 1 then P of 5 is to another we understand the P function and also the the two cases that can arise either we picked item or we don't let's combine the two into a recursion formula and remember that we want to pick whichever is best and best meaning whichever results in the maximum total weight so we define up J to be the maximum of picking job J then we get the the weight of job J + opt of the remaining intervals when we have removed the ones that overlap so we get up of P of J or the second option which is just disregarding item J and looking at the J minus one items so we want to have whichever is the maximum of those two and remember that when we have a recursion formula we always need to have a base case and the base case is that opt of zero is zero so let's get some more intuition by seeing how we use this algorithm on the same example so we form a table for each job 1 2 8 and also the the the P of J we want to find those values and the goal is then to calculate opt of J with the end goal of finding opt of n where n is equal to 8 items in this case so note also that all jobs here are sorted by finished times and the recursion formula which we saw in a previous slide so filling out the weights which are just given in the problem then we want to find P of J which is which we calculated on a previous slide but just to reiterate let's say that we look at say that we look of job seven then we notice here that all of these three overlap right because the finish time of each of those are greater than the starting time but for job three to n1 the finish time is less than or equal to the starting time of this and pfj is gives us the great the greatest index I so P of seven would be 3 and P of 7 is 3 and now to find opt of J we start from the beginning we want to find upped of one so up to one is the maximum of taking the job job one which has a total weight of three plus up of P of one and I notice here also that there's a parenthesis missing here but anyways so opt of P of 1 P of 1 we see it's just 0 so we get the maximum of three plus up to zero up to zero is the base case which is a zero so up to one is a maximum of three plus zero comma zero so it will just be three the second one up to is the maximum of 2 plus opt of P of 2 or opt of 1 so up P of 2 is 0 as well and up to one which is the previous item it's three so we get the maximum of two or three so either we pick item two that we cannot pick item one I mean item job one so we see here that we want to pick job one because it has a greater weight oh the up to will also have a value of three so similarly for the rest of these values in the table we simply use the same recurrence formula and calculate the rest and what we can see for example is that when this value changes we note that this means that we pick item I mean job six so job six has a optimal I mean has a weight of 5 and then we consider which are the ones we can choose if if we remove if we remove the overlapping ones so we pick job six then we have P of six which is one right we only have job one we can pick which has a opt one of three so it means that we take this one 5 plus the job 1 we get a total of 8 and we can see here that we don't want to sense the values here are the same we don't want to pick job 7 or job 8 but rather we ignore those and we pick job 6 instead and then remember that the goal is always to return opt of n which is the maximum weight for all of the items right so in the previous slide we saw that opt of 8 is is 8 and then one might ask well we want to find which I mean how do we find which which jobs or items we we picked well we use a backtracking so we check if if the W J plus opt of p FJ is greater than opt of J minus 1 so if we take that item if that results in a total total weight that is greater if we ignore that item that means that we add item J to the optimal solution and we instead look at opt of p FJ else we ignore this item and we look at the problem as a problem of the opt of J minus 1 so a quick look at the time complexity remember that we first sorted by finish time sorting is n log n then to find the P of J for each of the J values has a time complexity of o of n log n with a clever use of binary search the I think the straightforward approach would be oh of N squared so be careful when implementing that one you'll find the maximum maximal weight assuming that we have the the P vector and unless it's sorted this is a linear time this is linear time and also to backtrack to find optimal items this is also linear so the total will be O of n log n now that we understand the actual algorithm and how it works we're ready to implement it in Python so check out the next video if you want to see how we actually implement this algorithm