Finding the minimal coverage of an interval with subintervals

Question

Suppose I have an interval (a,b), and a number of subintervals {(a_i,b_i)}_i whose union is all of (a,b). Is there an efficient way to choose a minimal-cardinality subset of these subintervals which still covers (a,b)?

Answer 1

A greedy algorithm starting at a or b always gives the optimal solution.

Proof: consider the set S_a of all the subintervals covering a. Clearly, one of them has to belong to the optimal solution. If we replace it with a subinterval (a_max,b_max) from S_a whose right endpoint b_max is maximal in S_a (reaches furthest to the right), the remaining uncovered interval (b_max,b) will be a subset of the remaining interval from the optimal solution, so it can be covered with no more subintervals than the analogous uncovered interval from the optimal solution. Therefore, a solution constructed from (a_max,b_max) and the optimal solution for the remaining interval (b_max,b) will also be optimal.

So, just start at a and iteratively pick the interval reaching furthest right (and covering the end of previous interval), repeat until you hit b. I believe that picking the next interval can be done in log(n) if you store the intervals in an augmented interval tree.

Answer 2

Sounds like dynamic programming.

Here's an illustration of the algorithm (assume intervals are in a list sorted by ending time):

//works backwards from the end
int minCard(int current, int must_end_after)
{
    if (current < 0)
        if (must_end_after == 0)
            return 0; //no more intervals needed
        else
            return infinity; //doesn't cover (a,b)
        
    if (intervals[current].end < must_end_after)
        return infinity; //doesn't cover (a,b)
   
    return min( 1 + minCard(current - 1, intervals[current].start),
                    minCard(current - 1, must_end_after) );
    //include current interval or not?
}

But it should also involve caching (memoisation).