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