Given a set of intervals, find the minimum number of points that need to be placed, so that every interval has a point in it

Question

Suppose you are given a set of intervals, with the starting time of each interval as s subscript i and the finishing time of f subscript i. Find the minimum number of points that need to be placed to that every interval has a point.

I'm trying to find an algorithm that would solve this. I'm getting stuck when an interval that overlap two intervals, i.e starts halfway through one interval and ends halfway through another has an interval that is contained in it.

Thanks

Answer 1

1. Remove any intervals that completely contain a smaller interval. You can do this because, if the smaller interval is satisfied, then the larger interval must also be satisfied.
2. Sort intervals by s_i.
3. Starting from the first interval: place a point at f_i. This will satisfy the first interval, and any intervals that overlap it.
4. Continue in sorted order to the next interval that does not yet contain a point, and place a point at f_i.
5. Repeat.