运维开发网

ruby-on-rails – 检测Ruby中的重叠范围

运维开发网 https://www.qedev.com 2020-07-27 18:24 出处:网络 作者:运维开发网整理
我有一系列范围: [[39600..82800], [39600..70200],[70200..80480]] 我需要确定是否有重叠.在ruby中这是一个简单的方法吗? 在上述情况下,输出应为“重叠”. 这是一个非常有趣的难题,特别是如果你关心表演. 如果范围只有两个,那么这是一个相当简单的算法,它也包含在ActiveSupport overlaps?扩展中. def ranges_overla
我有一系列范围:

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

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

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

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

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

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

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

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

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

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

0

精彩评论

暂无评论...
验证码 换一张
取 消