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

**URL:** <https://www.ruby-forum.com/t/interval-relationships-was-re-range-overlap/86358>\
**Category:** Ruby\
**Created:** [February 21, 2007, 6:29pm UTC](https://www.ruby-forum.com/t/interval-relationships-was-re-range-overlap/86358 "2007-02-21T18:29:20Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![avdi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/c6cbf5/32.png) [@avdi](https://www.ruby-forum.com/u/avdi)\
**Post date:** [February 21, 2007, 6:29pm UTC](https://www.ruby-forum.com/t/interval-relationships-was-re-range-overlap/86358/1 "2007-02-21T18:29:20Z")

</div>

On 2/21/07, Pierre-Charles D. [removed\_email\_address@domain.invalid](mailto: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  
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.

---

<div class="post-metadata">

**Author:** ![avdi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/c6cbf5/32.png) [@avdi](https://www.ruby-forum.com/u/avdi)\
**Post date:** [February 21, 2007, 7:56pm UTC](https://www.ruby-forum.com/t/interval-relationships-was-re-range-overlap/86358/2 "2007-02-21T19:56:40Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![avdi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/c6cbf5/32.png) [@avdi](https://www.ruby-forum.com/u/avdi)\
**Post date:** [February 21, 2007, 8:06pm UTC](https://www.ruby-forum.com/t/interval-relationships-was-re-range-overlap/86358/3 "2007-02-21T20:06:44Z")

</div>

On 2/21/07, Pit C. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> end

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

Thanks!