4
$\begingroup$

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]$.

  • 0
    Same question at stackoverflow: http://stackoverflow.com/questions/3908139/need-effective-greedy-for-covering-a-line-segment2010-10-11

1 Answers 1

4

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.

  • 0
    That's what I thought also, but I am confused if the problem is interested in the number of segments only or that and the length of the segment need to be covered. Suppose we want to cove [0,12] segment, and there are 3 segments: [0,5],[5,12], [0,10]. Follow ur algorithm, it will take [0,10], then it does not cover all the segment, but if we take the other two, it will cover up.2010-10-11
  • 0
    Actually, once you have [0,10], the algorithm says to pick the segment with greatest right end and covered left end, which in this case is [5,12]. So you'd still cover the interval with two segments, though there would be more overlap.2010-10-11
  • 0
    there should be no overlaping2010-10-12
  • 0
    So... you're trying to minimize overlap? Or eliminate it? In most situations, the latter won't be possible.2010-10-12