如何组合重叠时间范围(时间范围联合)

Question

我有一个包含多个时间范围的数组:

[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]

我想获得具有重叠时间范围的相同数组,因此这种情况的输出将是:

[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]

因此,它会在时间范围重叠时创建新的时间范围,依此类推.如果他们不重叠,将保持分离.另一个例子:

输入:

[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]

输出(将是相同的,因为它们不重叠):

[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]

我在想一些递归方法,但我需要一些指导......

Answer 1

给定一个函数,如果两个范围重叠,则返回truthy:

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

(此功能由sepp2k和steenslag提供)

和一个合并两个重叠范围的函数:

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

那么这个函数,给定一个范围数组,返回一个新数组,其中任何重叠范围合并:

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

Answer 2

稍微搜索一下,我发现了一个可以解决问题的代码:

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

样本(使用时间范围!):

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

在此处找到:http://www.ruby-forum.com/topic/162010