In this problem, you are given n intervals [l_i, r_i] on a line. The goal is to find the minimum number of points on the line such that every interval contains at least 1 point. It's ok for a point to lie on the endpoint of any interval.

You can solve this with a greedy solution. It turns out we only have to select points that lie at either the left or right endpoints of a segment. Let's sort the segments by increasing r_i and perform sweep line on the sorted points. We maintain a value "farthest right point so far" called last. Initially last = -100005 (so last is less than any possible right endpoint). Then we process segments in sorted order. If a segment has a l_i < last, then we know it was already covered by a previous point and can skip it. If a segment has a l_i > last, then we need to select a point in the segment. We should place this nail as far right as possible (so set last = r_i). We repeat this process until there are no segments remaining.

Why should points be picked from right endpoints after sorting? (Why not pick any x_i where l_i <= x_i < r_i?) If we place a nail at x_i, then it's possible that the next segment lies at [l_(i+1), r_(i+1)] where l_(i+1) = r_(i+1) = r_i and it won't be covered by the last selected point. Only by picking the rightmost point can we avoid this.

Note that if we sort by left end point (l_i), we should process the segments in reverse order and select left endpoints instead of right.