Given n segments of line (into the $X$ axis) with coordinates $[li; ri]$. You are to choose the minimum number of segments that cover the segment $[0;M]$. All segment are within $[0,M]$.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I think the greedy algorithm will work. You have to cover 0, so search all segments with a left end of zero and take the longest. Now search all segments with a left end that you have already covered and take the one with the greatest right end. Continue until you hit M. At each stage you have a minimal solution for the range so far.
If overlap (see the comment below) is not allowed, you need a tree structure. Make a list of all the segments that have left end zero. For each one, attach all segments you can, that have the same left end as the existing right end. If you want, you can prune out paths that have as many or more segments than some other path with the same right endpoint. Continue to the end. Then search over all the paths for ones that reach M and take the shortest. I wouldn't call this a greedy algorithm (as called out in the Math Overflow version) but if overlap is not allowed we can't be sure that any given path will reach M.