Need effective greedy for covering a line segment

Question

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]. Design a greedy algorithm to solve this problem.

Here what I did: sorting them by starting points in increasing order, then I choose the longest one, second longest.... But here is a problem: Suppose we want to cove [0,12] segment, and there are 3 segments: [0,5],[5,12], [0,10]. Follow the 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.

Do you guys have any other idea? without sorting and taking longest lines does not work. we want to cover segment [0,12] and there are 5 segments: [0,2][2,10].[10,12], [0,6][6,12] Follow ur algo the first three are chosen but the last 2 r the optimal one

Answer 1

Do you guys have any other idea?

I can think of a really crappy N^N algorithm.

Answer 2

I assume that overlapping intervals are fine as long as it gives optimal answer.

Before I go further, I would like to ask, if you know why your greedy approach failed to give optimal answer? (think a minute before reading next paragraph.)

If you have not figured it out why, let me tell you. you always pick longest interval (after sorting), but it may not be the longest interval that covers uncovered interval segment. lets say you have 0-10, 5-14, 9-15. If you pick by longest interval then you are going to pick all segments. After you pick 1st segment, picking the 2nd one covers only 4 units extra whereas picking 3rd one covers 5 units extra. So its clear that picking based on longest interval length doesn't give optimal solution.

I think now you get the idea. Given that it is marked as homework, its not appropriate if I present solution beyond this point.

Answer 3

I don't think it needs to be a disjoint cover, or you can use an overlapping cover. In your example just take [0,10] and then [5,12]. First look at all of the segments starting at 0, then find the longest. We'll call this [0,m] next look at all line segments [a,b] such that am, take the one with the largest m. Continue iteratively in this manner. It will take |N|*|C|, where N is the number of line segments and c is the number of segments taken to cover the line.