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.)
How about a greedy algorithm?
ReplyDeleteConsider 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.)