Emilio Emilio - 5 months ago 29
Ruby Question

How to combine overlapping time ranges? (time ranges union)

Let´s say 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

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(ranges)
  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