将重叠范围分割为所有唯一范围
将重叠范围分割为所有唯一范围
提问于 2017-12-29 00:56:43
我试图将动态数量的范围与相关属性分开，这样每当有2个或更多的范围重叠时，重叠部分(S)就被分割成唯一的范围，并将所有重叠的属性组合在一起。更具体的说，我有
1-10 - attributes a
7-12 - attributes b
9-15 - attributes c我想做这个
1-6 - attributes a
7-8 - attributes a, b
9 - 10 - attributes a,b,c
11-12 - attributes b,c
13-15 - attributes c实际上，它可以归结为将样式应用于Office中的范围，但我相信任何场景都可以解决底层逻辑。谢谢你对如何处理这个问题的任何建议。我将使用node/javascript，但我认为任何演示该方法的语言都足够了。
回答 1
Software Engineering用户
回答已采纳
发布于 2017-12-29 03:05:28
以下是我要做的事：
- 制作一个三重态数组(n，attr，e)，每个给定间隔有两个元素。一个编码起始点，并有e=false，另一个编码结束点，并有e=true。
在您的示例中，您将拥有(1，a，false)，(10，a，true)，(7，b，false)，(12，b，true)，(9，c，false)，(15，c，true)。
- 按字典顺序对n和e数组进行排序(取false < true)
现在你有了(1，a，false)，(7，b，false)，(9，c，false)，(10，a，true)，(12，b，true)，(15，c，true)
- 现在遍历排序数组，保留“当前”属性集S(在开始时为空)。在每一步中，更新S，然后从数组中的两个连续元素输出间隔(必要时调整端点1，跳过空间隔)。换句话说，如果有一对连续的三胞胎(n，a，e)和(m，b，f)，那么步骤是：
- 如果e=false，添加一个到S，如果e=true，从S中取一个。
- 定义n'=n (如果e=false )或n'=n+1 ( e=true )
- 定义m'=m-1 (如果f=false )或m'=m (如果f=true )
- 如果n‘<= m'，输出(n'，m'，S)，否则什么都不输出。
在我们的示例中，输出将是(1,6，{a})，(7,8，{a，b})，(9,10，{a，b，c})，(11,12，{b，c})，(13,15，{c})。
页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://softwareengineering.stackexchange.com/questions/363091
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号