Minimizing the number of boxes that cover a given set of intervals

Question

Hi, this is a question for the algorithms gurus out there :-)

Let S be a set of intervals of the natural numbers that might overlap and b a box size. Assume that for each interval, the range is strictly less than b.

I want to find the minimum set of intervals of size b (let's call it M) so all the intervals in S are contained in the intervals of M.

Trivial example:

S = {[1..4], [2..7], [3..5], [8..15], [9..13]}
b = 10
M = {[1..10], [8..18]}
// so ([1..4], [2..7], [3..5]) are inside [1..10] and ([8..15], [9..13]) are inside [8..18]

I think a greedy algorithm might not work always, so if anybody knows of a solution to this problem (or a similar one that can be converted into), that would be great.

Thanks!

Update I've been thinking a little bit more about it, and maybe my first intuition was wrong and a greedy algorithm is just the way to solve this, as in the end all the intervals need to be covered and it wouldn't make any difference how the super-intervals are chosen... Should I delete the question or maybe somebody can assert this?

Answer 1

The algorithm might be the following.

1. a = 0
2. curr = lowest number in S that is > a. (In our case = 1. in [1..4])
3. Add an interval [curr..b] to M. (In our case M = {[1..10]} )
4. a = max upper bound in M. (In our case a = 10 )
5. Go to 2.

Answer 2

Yes, the greedy algorithm is optimal. Informally, consider an arbitrary solution M. We will transform it into a superset of the greedy solution M' without increasing the number of intervals. Repeatedly consider the leftmost interval I in M - M'. Let s be the leftmost interval in S for which I is the leftmost interval in M to contain s. The left-to-right greedy algorithm chooses an interval I' whose left edge is aligned with s's. I claim first that I' is to the right of I, since I' is the rightmost interval to contain s, and second, that M - {I} U {I'} is a valid solution, since the only intervals contained by I but not I' are to the left of s and thus already contained by some other interval. The number of intervals not in the greedy solution decreases, so we eventually reach the greedy solution.