Interval Scheduling Greedy Algorithm: Python

Key Takeaways

this video I want to walk through a pretty cool and simple algorithm and how to implement it in Python so the problem is that given a set of tasks where each task has a starting time and an ending time we want to compute the largest sub set of non-overlapping intervals so what that means is that we want to do as many of these tasks as possible but none of them can overlap each other and how we solve this which one can prove is by agree the algorithm which is that we pick the task with the earliest ending time first so in this case this one the first one has the earliest finish time which means that we pick that one and then what we want to do is that we want to disclude these the second and the third one because visually we can obviously see that the they overlap the first one which means that the finish time of this one is greater than the starting time of this one right for them to not overlap the finish time of this one needs to be less than or equal to the starting time of the other task all right so let's try to code this solution and let's see I've already copied the tasks here so or our four requests so what we want to and this these are the same as the image so for example our one is this one starts at zero and ends at three so the first one is the starting time second one is the ending time and then we want to put all of these in a list or eight like this and remember what we want to do is that we want to pick the earliest finish time first which means that we have to sort it and then also this is a list of tuples and we want to sort it by the second element so one can do this by using the lambda like this so we want to sort with the key lambda with X and we want to sort with the second element of the tuple all right and then we want to have an optimal solution which we call o where we will append the tasks or the requests which are in the optimal solution okay so then we want to define the role scheduling which takes a set of requests and also o the empty list and then the goal is that we want to have a turn oh so let's see you can call this here interval scheduling aren't oh I want to see oh and then you can print o all right so now to the actual algorithm what we want to do is that we can start we can start by having a finish time of zero and then we want to go through each request in R and remember these are sorted already by by finish time which we did here and then if the starting time of this one is greater or equal to the finish time of the one the one that we're currently looking at I remember we've initialize it at 0 as 0 then it means that it's a viable is next option right because then they don't overlap and we just go by the principle of taking the one that has the earlier finish time first and since it's already sorted that would be the next one in the list as long as they don't overlap so we look if finish is less than equal to R of 0 right this means that the finish time I'm the one that we're currently looking at and in this life as 0 is less than or equal to the starting time of R of 0 which will hold for the first one right 0 less than 0 if this is the case then the finish time we'll just set as the finish time of that particular task and we will append this to our optimal solution and believe it or not the algorithm is that simple this will provide us the optimal solution first I did it in a much more complicated way than this but this works so why not pick the simple one right so if we run this on the example of the image I have then it says that we should pick the tile the request o 3 3 6 & 8 10 so this means that we should pick this one right 0 2 3 then we disclude these two and we pick this one because it's had the earliest finish time so pick this one this one and then we pick since these are all not included pick the last one so the optimal solution are those three for for a total of three tasks alright I hope you enjoyed the video and see you in another one hopefully