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 of this problem (or a similar one that can be converted into), that would be great.

Thanks!