检测Ruby中的重叠范围

Question

我有一系列范围:

[[39600..82800], [39600..70200],[70200..80480]]

我需要确定是否有重叠.在ruby中这是一个简单的方法吗？

在上述情况下,输出应为"重叠".

Answer 1

这是一个非常有趣的难题,特别是如果你关心表演.

如果范围只有两个,那么它是一个相当简单的算法,ActiveSupport overlaps?扩展也包含在内.

def ranges_overlap?(r1, r2)
  r1.cover?(r2.first) || r2.cover?(r1.first)
end

如果你想比较多个范围,这是一个相当有趣的算法练习.

您可以遍历所有范围,但是您需要将每个范围与所有其他可能性进行比较,但这是一种具有指数成本的算法.

更有效的解决方案是对范围进行排序并执行二进制搜索,或者使用数据结构(例如树)来计算重叠.

Interval树页面中也解释了此问题.计算重叠主要包括找到树的交叉点.

Answer 2

这不是一个办法吗？

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