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 $l_{m} ≤ x ≤ r_{m}$. If $x = r_{m}$, then we are done. Otherwise, $x < r_{m}$. In this case, we can replace $x$ by $r_{m}$ in $S$.