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)?

Solution 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.

Solution 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).

Comments

[jfs]

minCard() is intended to get a minimal cardinality but the question asks for a subset with minimal cardinality.

[jfs]

Could you elaborate: "the remaining uncovered interval (bmax,b) will be a subset of the remaining interval from the optimal solution"?

[Artelius]

It would just be an extension of this algorithm that also keeps track of which subset was used to form that optimum value.

[leo7r]

@JFS: Suppose that the optimal solution starts with an interval (ai,bi) that covers (a,bi) and leaves (bi,b) uncovered. From the definition of (amax,bmax) we have that bmax>=bi, so (bmax,b) is a subset (subinterval) of (bi,b).

[user183037]

"If we replace it with a subinterval (amax,bmax) from Sa...": Do you mean the sub-interval (amin, bmax)? And I'm not so sure about (bmax, b) either.

[leo7r]

@user183037 The 'max' is just an index for the whole interval. Interval 'foo' is (a_foo,b_foo). (b_max,b) is the remaining interval.

[Sumeet_Jain]

@Artelius What is the complexity of your algorithm ?

[Artelius]

The complexity is O(n^2) in the worst case. For example when all intervals have an identical end point but different start points, all of those start points are going to propagate back to the beginning. The greedy approach is better.

[greybeard]

Where in the question does time rear its daunting head?