如何合并重叠的时间范围（时间范围工会）

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

某种算法可能有所帮助：

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 

Answer 3

你不只是想从数组集合中找到最小的第一个值和最大的最后一个值？

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] 

Answer 4

搜索一点点我发现，做的伎俩代码：

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

Answer 5

方面宝石有Range.combine方法可能有用：http://rdoc.info/github/rubyworks/facets/master/Range#combine-instance_method

Answer 6

除少数用例外，标记答案的效果很好。这样一个用例是

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

在ranges_overlap条件不处理这个用例。所以我写了这个

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 

这是处理所有的边缘情况对我来说至今。

Answer 7

@ wayne-conrad提供的解决方案非常好。我实施它的问题，我偶然发现。然后我实现了一个迭代版本并对这两者进行了基准测试。看来，迭代版本更快。注意：我使用ActiveSupport作为Range#overlaps?和时间帮助器，但实现纯Ruby版本是微不足道的。

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)