Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Same question at stackoverflow: stackoverflow.com/questions/3908139/… –  Aryabhata Oct 11 '10 at 16:50

1 Answer 1

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.

share|improve this answer
    
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. –  user1997 Oct 11 '10 at 17:05
    
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. –  Paul VanKoughnett Oct 11 '10 at 17:43
    
there should be no overlaping –  user1997 Oct 12 '10 at 0:16
    
So... you're trying to minimize overlap? Or eliminate it? In most situations, the latter won't be possible. –  Paul VanKoughnett Oct 12 '10 at 21:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.