检测Ruby中的重叠范围
我有一系列范围：
[[39600..82800], [39600..70200],[70200..80480]] 我需要确定是否有重叠。在ruby中这样做的简单方法是什么？
在上述情况下，输出应为“重叠”。
这是一个非常有趣的难题，特别是如果你关心表演。
如果范围只有两个，那么这是一个相当简单的算法， ActiveSupport overlaps?也包含了ActiveSupport算法overlaps? 延期。
def ranges_overlap?(r1, r2) r1.cover?(r2.first) || r2.cover?(r1.first) end
如果你想比较多个范围，这是一个相当有趣的算法练习。
您可以遍历所有范围，但是您需要将每个范围与所有其他可能性进行比较，但这是一种具有指数成本的算法。
更有效的解决方案是对范围进行排序并执行二进制搜索，或使用数据结构（例如树）来计算重叠。
Interval树页面也解释了这个问题。 计算重叠主要包括找到树的交叉点。
考虑一下：
class Range include Comparable def <=>(other) self.begin <=> other.begin end def self.overlap?(*ranges) edges = ranges.sort.flat_map { |range| [range.begin, range.end] } edges != edges.sort.uniq end end Range.overlap?(2..12, 6..36, 42..96) # => true
备注 ：
- 这可以采用任意数量的范围。
- 看一下使用代码进行一些测试的要点 。
- 代码创建一个包含每个范围的开始和结束的平面数组。
- 如果不重叠，该数组将保留订单。 （用一些例子比用文字解释原因更容易想象，试试吧）。
这不是一种方法吗？
def any_overlapping_ranges(array_of_ranges) array_of_ranges.sort_by(&:first).each_cons(2).any?{|x,y|x.last>y.first} end p any_overlapping_ranges([50..100, 1..51,200..220]) #=> True
为了简单和可读性，我建议这种方法：
def overlaps?(ranges) ranges.each_with_index do |range, index| (index..ranges.size).each do |i| nextRange = ranges[i] unless index == i if nextRange and range.to_a & nextRange.to_a puts "#{range} overlaps with #{nextRange}" end end end end r = [(39600..82800), (39600..70200),(70200..80480)] overlaps?(r)
和输出：
ruby ranges.rb 39600..82800 overlaps with 39600..70200 39600..82800 overlaps with 70200..80480 39600..70200 overlaps with 70200..80480