How to combine overlapping time ranges (time ranges union)

Question

I have an array with several time ranges inside:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
 Tue, 24 May 2011 16:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00,
 Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 09:00:00 CEST +02:00,
 Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

I want to get the same array with the overlapping time ranges combined, so the output for this case will be:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
 Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

So it creates a new time range when to time ranges overlap, and so on. If they don´t overlap the will be keep separated. Another example:

Input:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
 Tue, 24 May 2011 16:00:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

Output (will be the same because they don´t overlap):

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
 Tue, 24 May 2011 16:00:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

I was thinking in some recursive approach, but I need some guidance here...

score 35 · Accepted Answer · edited Aug 21 '17 at 13:48

Given a function that returns truthy if two ranges overlap:

def ranges_overlap?(a, b)
  a.include?(b.begin) || b.include?(a.begin)
end

(this function courtesy of sepp2k and steenslag)

and a function that merges two overlapping ranges:

def merge_ranges(a, b)
  [a.begin, b.begin].min..[a.end, b.end].max
end

then this function, given an array of ranges, returns a new array with any overlapping ranges merged:

def merge_overlapping_ranges(overlapping_ranges)
  overlapping_ranges.sort_by(&:begin).inject([]) do |ranges, range|
    if !ranges.empty? && ranges_overlap?(ranges.last, range)
      ranges[0...-1] + [merge_ranges(ranges.last, range)]
    else
      ranges + [range]
    end
  end
end

I think is only fair to mark this as the right answer. Especially after YWCA Hello finding, besides the code looks cleaner. — PakitoV, Aug 18 '15 at 06:50

score 5 · Answer 2 · answered May 17 '11 at 09:38

Searching a little bit I have found a code that does the trick:

def self.merge_ranges(ranges)
  ranges = ranges.sort_by {|r| r.first }
  *outages = ranges.shift
  ranges.each do |r|
    lastr = outages[-1]
    if lastr.last >= r.first - 1
      outages[-1] = lastr.first..[r.last, lastr.last].max
    else
      outages.push(r)
    end
  end
  outages
end

A sample (working with time ranges too!):

ranges = [1..5, 20..20, 4..11, 40..45, 39..50]
merge_ranges(ranges)
=> [1..11, 20..20, 39..50]

Found here: http://www.ruby-forum.com/topic/162010

This algorithm has potential issues. For instance, it assumes that (1..3) and (4..6) overlap. — YWCA Hello, Mar 11 '15 at 18:19

score 4 · Answer 3 · answered Oct 16 '20 at 02:58

You can do it by using multi_range gem.

Example 1:

ranges = [
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 13:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 16:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 09:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 15:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
]

MultiRange.new(ranges).merge_overlaps.ranges
# => [2011-05-24 08:00:00 +0800..2011-05-24 13:00:00 +0800, 2011-05-24 15:30:00 +0800..2011-05-24 18:00:00 +0800]

Example 2:

ranges = [
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00')..Time.parse('Tue, 24 May 2011 13:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 16:00:00 CEST +02:00')..Time.parse('Tue, 24 May 2011 18:00:00 CEST +02:00'),
]

MultiRange.new(ranges).merge_overlaps.ranges
# => [2011-05-24 08:00:00 +0800..2011-05-24 13:00:00 +0800, 2011-05-24 16:00:00 +0800..2011-05-24 18:00:00 +0800]

score 2 · Answer 4 · answered Jun 10 '14 at 20:17

2

The facets gem has Range.combine method that may be of use: http://rdoc.info/github/rubyworks/facets/master/Range#combine-instance_method

answered Jun 10 '14 at 20:17

subelsky

405
6
12

Alexander Popov · Answer 5 · 2017-08-21T15:07:51.413

The solution, offered by @wayne-conrad is a very good one. I implemented it for a problem, I stumbled upon. Then I implemented an iterative version and benchmarked the two. It appears, the iterative version is quicker. Note: I use ActiveSupport for Range#overlaps? and the time helpers, but it is trivial to implement a pure-Ruby version.

require 'active_support/all'

module RangesUnifier
  extend self

  # ranges is an array of ranges, e.g. [1..5, 2..6] 
  def iterative_call(ranges)
    ranges.sort_by(&:begin).reduce([ranges.first]) do |merged_ranges, range|
      if merged_ranges.last.overlaps?(range)
        merged_ranges[0...-1] << merge_ranges(merged_ranges.last, range)
      else
        merged_ranges << range
      end
    end
  end

  def recursive_call(ranges)
    return ranges if ranges.size == 1

    if ranges[0].overlaps?(ranges[1])
      recursive_call [merge_ranges(ranges[0], ranges[1]), *ranges[2..-1]]
    else
      [ranges[0], *recursive_call(ranges[1..-1])]
    end
  end

  def merge_ranges(a, b)
    [a.begin, b.begin].min..[a.end, b.end].max
  end
end

five_hours_ago = 5.hours.ago
four_hours_ago = 4.hours.ago
three_hours_ago = 3.hours.ago
two_hours_ago = 2.hours.ago
one_hour_ago = 1.hour.ago
one_hour_from_now = 1.hour.from_now
two_hours_from_now = 2.hours.from_now
three_hours_from_now = 3.hours.from_now
four_hours_from_now = 4.hours.from_now
five_hours_from_now = 5.hours.from_now

input = [
  five_hours_ago..four_hours_ago,
  three_hours_ago..two_hours_from_now,
  one_hour_ago..one_hour_from_now,
  one_hour_from_now..three_hours_from_now,
  four_hours_from_now..five_hours_from_now
]

RangesUnifier.iterative_call(input) 
#=> [
# 2017-08-21 12:50:50 +0300..2017-08-21 13:50:50 +0300, 
# 2017-08-21 14:50:50 +0300..2017-08-21 20:50:50 +0300, 
# 2017-08-21 21:50:50 +0300..2017-08-21 22:50:50 +0300
# ]

RangesUnifier.recursive_call(input)
#=> [
# 2017-08-21 12:50:50 +0300..2017-08-21 13:50:50 +0300, 
# 2017-08-21 14:50:50 +0300..2017-08-21 20:50:50 +0300, 
# 2017-08-21 21:50:50 +0300..2017-08-21 22:50:50 +0300
# ]

n = 100_000    

Benchmark.bm do |x|
  x.report('iterative') { n.times { RangesUnifier.iterative_call(input) } }
  x.report('recursive') { n.times { RangesUnifier.recursive_call(input) } }
end

# =>
#        user     system      total        real
# iterative  0.970000   0.000000   0.970000 (  0.979549)
# recursive  0.540000   0.010000   0.550000 (  0.546755)

score 1 · Answer 6 · answered Mar 24 '18 at 22:13

The gem range_operators does a wonderful job by adding missing features to the Ruby Range class. It is way smaller than adding the whole facets gem.

I your case the solution would be the rangify method, which is added to the Array class and would do exactly what you are looking for.

score 1 · Answer 7 · answered Oct 25 '19 at 23:34

I made a minor update to the answer from Wayne Conrad to handle edge cases involved with open-ended arrays (created with ... operator instead of .. operator).

I changed the name to merge_continuous_ranges since while ranges like 0...1 and 1..2 do not overlap, their combined ranges are continuous, so it makes sense to combine them:

def merge_continuous_ranges(ranges)
  ranges.sort_by(&:begin).inject([]) do |result, range|
    if !result.empty? && ranges_continuous?(result.last, range)
      result[0...-1] + [merge_ranges(result.last, range)]
    else
      result + [range]
    end
  end
end

def ranges_continuous?(a, b)
  a.include?(b.begin) || b.include?(a.begin) || a.end == b.begin || b.end == a.begin
end

def merge_ranges(a, b)
  range_begin = [a.begin, b.begin].min
  range_end = [a.end, b.end].max

  exclude_end = case a.end <=> b.end
  when -1
    b.exclude_end?
  when 0
    a.exclude_end? && b.exclude_end?
  when 1
    a.exclude_end?
  end

  exclude_end ? range_begin...range_end : range_begin..range_end
end

score 1 · Answer 8 · answered May 16 '11 at 12:59

1

Some kind of algorithm that might help:

Sort range array by start time (r1, r2, r3, r4, .. rn)

for each range pair [r1, r2], [r2, r3] .. [rn-1, rn]:
    if r1_end > r2_start: # they overlap
        add [r1_start, r2_end] to new range array
    else: # they do not overlap
        add [r1] and [r2] to new range array (no changes)

startover with the new range array until no more changes

answered May 16 '11 at 12:59

arnep

5,971
3
35
51

1

Thanks, I have found a working solution, but as a new user I cannot answer my own question within 8 hours. Will do that tomorrow. – PakitoV May 16 '11 at 13:15
1

Good job with the pseudo-code for a language-specific question! – awendt May 17 '11 at 07:06

ccyrille · Answer 9 · 2023-02-02T19:53:49.123

A solution in one method and bug-free for what I can tell:

def merge_ranges(ranges)
  ranges = ranges.sort_by(&:first)
  merged = [ranges[0]]

  ranges.each do |current|
    previous = merged[-1]
    if current.first <= previous.last
      merged[-1] = previous.first..[previous.last, current.last].max
    else
      merged.push(current)
    end
  end

  merged
end

Usage:

ranges = [
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 13:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 16:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 09:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 15:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
]
merge_ranges(ranges)

#=> [2011-05-24 08:00:00 +0200..2011-05-24 13:00:00 +0200, 2011-05-24 15:30:00 +0200..2011-05-24 18:00:00 +0200]

Disclaimer: it's a port of https://stackoverflow.com/a/43600953/807442

score 0 · Answer 10 · answered Jun 21 '16 at 12:59

0

The Marked answer works well except for few use cases. One of such use case is

[Tue, 21 June 13:30:00 GMT +0:00..Tue, 21 June 15:30:00 GMT +00:00,
Tue, 21 June 14:30:00 GMT +0:00..Tue, 21 June 15:30:00 GMT +00:00]

The condition in ranges_overlap does not handle this use case. So I wrote this

def ranges_overlap?(a, b)
    a.include?(b.begin) || b.include?(a.begin) || a.include?(b.end) || b.include?(a.end)|| (a.begin < b.begin && a.end >= b.end) || (a.begin >= b.begin && a.end < b.end)
end

This is handling all the edge cases for me so far.

answered Jun 21 '16 at 12:59

Taher

732
1
9
26

I am using class, and this worked: `def ranges_overlap?(a, b) (a).cover?((b).begin) || (b).cover?((a).begin) || (a).cover?((b).end) || (b).cover?((a).end)|| ((a).begin < (b).begin && (a).end >= (b).end) || ((a).begin >= (b).begin && (a).end < (b).end) end` – Fernando Fabreti Mar 28 '17 at 17:39
I simplified my code a little bit and now this works for me `def has_overlap?(range_a, range_b)` `range_a.last > range_b.first && range_a.first < range_b.last` `end` – Taher Apr 03 '17 at 07:39

score 0 · Answer 11 · answered May 16 '11 at 15:32

Dont you just want to find the smallest first value and the largest last value from the set of arrays?

ranges = [Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
 Tue, 24 May 2011 16:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00,
 Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 09:00:00 CEST +02:00,
 Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

union = [ranges.collect(&:first).sort.first, ranges.collect(&:last).sort.last]

No, that´s not what I was trying, the first output in my question was wrong (I wrote one range but should be two of them), that may have confuse you. Thank you for your answer anyway. — PakitoV, May 17 '11 at 09:50

How to combine overlapping time ranges (time ranges union)

11 Answers11

Linked