我正在开发一种编程语言,我想为其提供一个Range 数据类型,目前它不是通常的int
对列表。值 (x,y)
约束条件是 x < y
.我说不像通常那样,因为通常一个范围只是一对,但在我的例子中,它超过了,例如允许有
1 to 5, 7 to 11, 13 to 22
所有内容都包含在一个对象中。
我想提供两个函数来生成两个范围的并集和交集,它们应该包含来自几个范围的最少数量的非重叠间隔。例如
1 to 5 || 3 to 8 = 1 to 8
1 to 5 && 3 to 8 = 3 to 5
(1 to 3, 4 to 8) && 2 to 6 = (2 to 3, 4 to 6)
哪里||
是工会和&&
是交集。
如前所述,目前它们的实现只是一个列表。我知道存在更合适的数据结构(区间树),但现在我更关心从其他列表的并集/交集构建新列表列出..
实现这两个功能的最先进算法是什么?
提前致谢
最佳答案
由于您不想处理区间树而只使用列表,我建议您将范围表示保留为按 x 坐标排序的不相交区间的列表。
给定两个列表,您可以通过执行一种合并步骤来计算并集和交集,就像我们在合并排序列表时所做的那样。
例子:
对于 L1 和 L2 的并集:
创建 L 为空列表。
从L1和L2中取出x最小的区间放到L上。
现在再次取最小值,与 L 的最后一个元素进行比较,并决定是否需要将它们合并(如果重叠)或在 L 的末尾附加一个新的区间(如果它们不重叠)并继续处理,例如我们合并两个排序列表。
完成后,L 将是区间按 x 排序且不相交的并集。
对于交集,你可以做类似的事情。
关于algorithm - 范围交集/联合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3208110/