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

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
4dea430d31b993abaf41cd9b54f8128d?d=identicon&s=25 Avdi Grimm (Guest)
on 2007-02-21 18:29
(Received via mailing list)
On 2/21/07, Pierre-Charles David <pcdavid@gmail.com> 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.
93d566cc26b230c553c197c4cd8ac6e4?d=identicon&s=25 Pit Capitain (Guest)
on 2007-02-21 19:56
(Received via mailing list)
Avdi Grimm 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
4dea430d31b993abaf41cd9b54f8128d?d=identicon&s=25 Avdi Grimm (Guest)
on 2007-02-21 20:06
(Received via mailing list)
On 2/21/07, Pit Capitain <pit@capitain.de> wrote:
>    end
>
>
Very slick!  And an interesting example of Array auto-splatting (or
whatever
it's called...) in the inject block.

Thanks!
This topic is locked and can not be replied to.