Solution: Collecting Signatures

Solutions for the Collecting Signatures Problem.

Solution 1: Find a segment with the smallest right end

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

It must cover the segment [lm[l_{m},rm]r_{m}], therefore, SS contains a point xx such that lmxrml_{m} ≤ x ≤ r_{m}. If x=rmx = r_{m}, then we are done. Otherwise, x<rmx < r_{m}. In this case, we can replace xx by rmr_{m} in SS.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.