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].
Pubblicato da a
Reazioni: 

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

    ReplyDelete

Subscribe to: Post Comments (Atom)