Finding the minimum number of points spanning a whole set of intervals?

Question

Given the set of intervals [x,y] where 0 <= x,y <= 2000 , how can I find the minimum number of points that can cover (that is, each interval must contain at least one point in the resulting set of points) all intervals?

Example:

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

then the answer should be 2 (the minimum number of points needed to cover all intervals), since the points x=3,x=7 are one of the solutions.

Answer 1

You can use the greedy algorithm:

• Sort all intervals by their end points (in ascending order).

• Iterates over a sorted array of intervals. When the interval is completed, there are two options:

  • This is already affected. Nothing should be done in this case.
  • Until it is covered. Then the endpoint of this interval should be inserted into the result set.

The result set generated by this algorithm is optimal.