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

Announcement (2017-05-07): is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see and for other Rails- und Ruby-related community platforms.
Avdi G. (Guest)
on 2007-02-21 19:29
(Received via mailing list)
On 2/21/07, Pierre-Charles D. <removed_email_address@domain.invalid> 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.
Pit C. (Guest)
on 2007-02-21 20:56
(Received via mailing list)
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]]

Avdi G. (Guest)
on 2007-02-21 21:06
(Received via mailing list)
On 2/21/07, Pit C. <removed_email_address@domain.invalid> wrote:
>    end
Very slick!  And an interesting example of Array auto-splatting (or
it's called...) in the inject block.

This topic is locked and can not be replied to.