ruby-on-rails - 检测 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

如果要比较多个范围，这是一个相当有趣的算法练习。

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

一个更有效的解决方案是 order the ranges并执行二进制搜索，或使用数据结构(例如树)来计算重叠。

这个问题在 Interval tree 中也有解释。页。计算重叠本质上包括找到树的交集。