Minimizing the number of boxes that cover a given set of intervals
- by fortran
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!
