ruby-on-rails – 检测Ruby中的重叠范围
发布时间：2020-12-17 01:50:50 所属栏目：百科 来源：网络整理
导读：我有一系列范围： [[39600..82800],[39600..70200],[70200..80480]] 我需要确定是否有重叠.在ruby中这是一个简单的方法吗？ 在上述情况下,输出应为“重叠”. 解决方法 这是一个非常有趣的难题,特别是如果你关心表演. 如果范围只有两个,那么这是一个相当简单
|
我有一系列范围：
[[39600..82800],[39600..70200],[70200..80480]] 我需要确定是否有重叠.在ruby中这是一个简单的方法吗？ 在上述情况下,输出应为“重叠”. 解决方法
这是一个非常有趣的难题,特别是如果你关心表演.
如果范围只有两个,那么这是一个相当简单的算法,它也包含在 def ranges_overlap?(r1,r2) r1.cover?(r2.first) || r2.cover?(r1.first) end 如果你想比较多个范围,这是一个相当有趣的算法练习. 您可以遍历所有范围,但是您需要将每个范围与所有其他可能性进行比较,但这是一种具有指数成本的算法. 更有效的解决方案是order the ranges并执行二进制搜索,或使用数据结构(例如树)来计算重叠. 在Interval tree页面中也解释了此问题.计算重叠主要包括找到树的交叉点. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |