Solution: Collecting Signatures

Solution 1: Find a segment with the smallest right end

Consider the smallest ending point of a segment: $r_{m}$ = min$\{$$r_{1}$,…,$r_{n}$$\}$. We claim that there exists an optimum solution containing the point $r_{m}$. To prove this, we take an optimum solution $S$.

It must cover the segment $[l_{m}$,$r_{m}]$, therefore, $S$ contains a point $x$ such that $$ ...