Monday, March 16, 2009

Segment covering

Given several segments of line with coordinates [Li,Ri], choose the minimal amount of them, such they completely cover the segment [0,M].

1 comment:

  1. How about a greedy algorithm?

    Consider the position M, which is the last bit of the segment [0,M] that needs to be covered. We need to choose a segment to cover M, and regardless of which segment we choose, the cost is 1. So we can do no better than select the segment that covers M and has the smallest value of Li. Then repeat this greedy process on the remaining uncovered part, [0,Li-1].

    (This is NlogN time - just sort the N segments by their Ri values, then scan through the sorted list in descending order of Ri, keeping track of which segment scanned through so far has the smallest Li.)