如何组合重叠的时间范围(时间范围联合) [英] How to combine overlapping time ranges (time ranges union)

问题描述

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

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:

输入:

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

推荐答案

给定一个函数，如果两个范围重叠则返回真实:

Given a function that returns truthy if two ranges overlap:

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

(此功能由 sepp2k 和 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

这篇关于如何组合重叠的时间范围(时间范围联合)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！