[MUSIC] The next problem we're going to solve is called the activity selection problem. In this case, the input consists of several segments on a line. And what we would like to find in this case is the maximum subset, the maximum sized subset of them, such that no two of the selected segments overlap. So the real-life application of this problem is the following. Imagine that we have a meeting room, and we have several groups of people that would like to organize a meeting in this room. So for each meeting, we know its start time and its end time. And we would like to satisfy as many slide show requests as possible with the natural constraints, so two meetings cannot overlap. So two time intervals should not overlap, okay? So let's consider an example. So I assume that we're given four segments, from 2 to 6, from 1 to 4, from 7 to 9, and from 3 to 8. So in this case, the maximum number of non-overlapping segments that we can select out of these four segments is equal to two. For example, we can select the second segment and this the third one. It is not difficult to check that they do not overlap. Let me also show you, and as an example, so in this case we are given 11 segments. So they're all segments on a line, but we show them at different heights just so that they do not overlap, okay? So out of these 11 segments, it is possible to select 5 non-overlapping segments that are shown here in red. And we will soon convince ourselves that it is indeed the optimum weight, okay? So unlike the previous two problems, the previous two problems that we can see right now is the largest number problem and the minor change problem. In this case, it is not even straightforward what is the greatest strategy, right? But let's just try to guess. For example, one might want to take the shorter segment in their solution. Just with the hope that a shorter segment has as few conflicts with other segments as possible. Or on the other hand, we might also want to take the segment with the minimum left endpoint. I mean, that way, the meeting that starts as early as possible. Another guess is, probably we should take first the segment with the smallest right endpoint. That is the meeting that ends as early as possible. So it turns out that the first two strategies do not work in this case. So let me give you a counterexample for the first strategy. So let me remind you, the first strategy is that we should first take shorter segments. So consider these small data set consisting of just three segments. So if we take the shortest segment into our solution in this particular case, this is a middle segment, this will not allow us to take any other segment, because the shorter one here intersect any other segment, right? So if we take the middle one, we get a solution of size one. At the same time, it is not difficult to see that there is a solution in this case consisting of two segments, the top one and the bottom one, okay? So in this case, the shortest segment intersects all other segments. So it actually doesn't make any sense to take it into our solution. As for the second strategy, which suggests us to take a segment with the smallest left endpoint, consider the following counterexample. So the top segment here has the smallest left endpoint, right? And if we take it into our solution, we will lose the possibility to take any other segment into your solution, right? So we would take the top segment into the solution, but yet a solution of size one. And again, it is a suboptimal solution in this case, just because we can take into solution to other segments, okay? So as you might probably guess already, the start greedy strategy actually works. So let's just prove it formally. So what we're going to prove is that there exists an optimal solution that contains a segment with the minimum right endpoint. In other words, so if we just take it into our solution, then we can still extend it into an optimal solution, okay? So let's prove it formally. Let's denote by [a, b] the segment with the minimum right endpoint, and consider some optimum solution S. And assume that [c, d] is the segment from this solution S with its minimum right endpoint. So [c, d] is the segment from S, whose right point is minimum, okay? So we would like, first of all, there is a case when [a, b] coincides with [c, d]. So in this case, there is nothing to prove, right? So I assume there is even a more general case. So if d is equal to b, then this means that [c, d] is also a segment whose right endpoint is minimal. And in this case, there is nothing to prove. So I assume that d is actually greater than b. So what we need to show is that there still exists some other optimal solution that includes, for example, the segment [a, b], okay? And you might probably already guessed what we are going to do. So let's just remove the segment [c, d] from S and let's instead add the segment [a, b] into our solution. So in other words, let's replace the segment [c, d] with the segment [a, b]. Okay, so what I claim is that first of all, the size of the resulting solution is the same as the size of S, right, because we just replaced one segment. What I would like to also claim is that it is still a solution is that the new segment [a, b] does not overlap any other segments. So why is that? This is just because [c, d] does not overlap any other segment in S. And for this reason [a, b] also does not overlap, so why is that? Well, [a, b] lies, b is smaller than d, right? So this means that [a, b] in a sense, lies to the left of the point d. On the other hand, all other segments in the solution S, they lie to the right from d. This is just because [c, d] does not overlap any other segment. So if [c, d] does not overlap any other segment in S, then for sure, [a, b] also does not overlap any other segment. Which actually proves that there is an optimum solution that contains a segment [a, b], because right point is minimum, okay? Let me also illustrate the last part of this proof visually. So consider this data set, and now consider two highlighted segments. The first one, the red one, is from our current solution of size five. And the blue one is the initial segment whose right point is minimum that does not belong to the current optimum solution. So what you see here is that, if you swap these two segments, I mean, if you include the blue segment into our solution. And if you exclude the red one, then the resulting solution is still a solution, and the size is still five, right? So replacing this red segment with a blue segment cannot introduce any conflicts, okay? Now let me briefly mention how to implement this idea. Well, this can be done in a straightforward fashion. So we know that there exists an optimal solution containing the segment with the smallest right endpoint. So we just scan our end segments. We find the segment with the smallest right endpoint. We then include into our solution, and then we scan the whole list of segments once again and remove all the segments that are intersected by the current segment. Okay, and we'll repeat this procedure while the current set of segments is non-empty. This gives us an algorithm with the quadratic running time. Why is that? Well, just because we need to repeat this procedure n times, and at each iteration, we need two scans. First to find the minimum right endpoint, and then to remove all the segments that are intersected by the current segment.