Interval relationships (Was: Re: Range#overlap?)

Ruby
1

On 2/21/07, Pierre-Charles D. [email protected] wrote:

FWIW, people working with temporal logics and event algebras define 13
possible relationships between two intervals (see Fig. 4 page 10 of
[1]), with a precise (if not always intuitive) vocabulary.

Very interesting. As it happens I was thinking about algorithms for
sets of
intervals just this morning, for a personal project of mine. Do you
have
any more resources you could share on this topic?

In particular I’m looking for the most straightforward way to
consolidate a
set of intervals such that the resulting set is composed of the smallest
number of non-contiguous, non-overlapping intervals that encompass all
of
the starting intervals. E.g.:

— 
   |---|
          |---|
         |------|

would become:

|---------|
|------|

Any insight you could provide would be much appreciated.

2

Avdi G. schrieb:

would become:

|---------|
|------|

Avdi, here’s one way (based on your example above):

def combine(intervals)
intervals.sort.inject([]) { |result, (from, to)|
if result.empty? or from > result.last[1]
result << [from, to]
elsif to > result.last[1]
result.last[1] = to
end
result
}
end

p combine([[0, 4], [2, 6], [6, 10], [13, 17], [12, 19]])

=> [[0, 10], [12, 19]]

Regards,
Pit

3

On 2/21/07, Pit C. [email protected] wrote:

end

Very slick! And an interesting example of Array auto-splatting (or
whatever
it’s called…) in the inject block.

Thanks!