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?