Jac*_*ack 3 language-agnostic algorithm union intersection range
我正在开发一种编程语言,我想提供一种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)
||联合在哪里,&&是交叉点.
现在,他们的实现,如前所述,只是一个列表..我知道存在一个更合适的数据结构(区间树)但是现在我更关心从其他列表的联合/交集构建新列表.
哪些是实现这两个功能的最先进算法？
提前致谢
小智 7
由于您不想处理间隔树并且只使用列表,我建议您将范围表示保存为按x坐标排序的不相交间隔列表.
给定两个列表,您可以通过执行一种合并步骤来计算联合和交集,就像我们在排序列表的合并中一样.
例:
对于L1和L2的联合:
创建L为空列表.
取L1和L2中最小x的间隔并放到L.
现在再次取最小值,与L的最后一个元素进行比较,并确定它们是否需要在L的末尾合并(如果重叠)或附加的新间隔(如果它们不重叠)并继续处理,就像我们在合并两个排序列表.
一旦完成,L将成为联合,其间隔按x排序并且是不相交的.
对于交叉路口,您可以做类似的事情.