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

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
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
the starting intervals. E.g.:


would become:


Any insight you could provide would be much appreciated.

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

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

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


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


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


This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs