Finding minimum number of points which covers enti

问题:

Given a set of intervals [x,y] where 0 <= x,y <= 2000 how to find minimum number of points which can cover(i.e. Every interval should contain at least one point in resultant set of points) all intervals?

example:

Given Set of intervals:
    [2,5]
    [3,7]
    [7,10]

then answer should be 2 (minimum number of points required to cover all intervals) as points x=3,x=7 is one solution.

回答1:

You can use a greedy algorithm:

1. Sort all intervals by their end points(in increasing order).

2. Iterate over a sorted array of intervals. When an interval is over, there are two options:

   1. It is already covered by some point. Nothing should be done in this case.
   2. It is not covered yet. Then the end point of this interval should be inserted into to the resulting set.

The resulting set generated by this algorithm is optimal.