How to combine overlapping time ranges (time range

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...

Answer 1

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

Answer 2

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

Answer 3

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.