algorithm - 范围交集/联合

Question

我正在开发一种编程语言，我想为其提供一个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)

哪里||是工会和&&是交集。

如前所述，目前它们的实现只是一个列表。我知道存在更合适的数据结构(区间树)，但现在我更关心从其他列表的并集/交集构建新列表列出..

实现这两个功能的最先进算法是什么？

提前致谢

Answer 1

由于您不想处理区间树而只使用列表，我建议您将范围表示保留为按 x 坐标排序的不相交区间的列表。

给定两个列表，您可以通过执行一种合并步骤来计算并集和交集，就像我们在合并排序列表时所做的那样。

例子:

对于 L1 和 L2 的并集:

创建 L 为空列表。

从L1和L2中取出x最小的区间放到L上。

现在再次取最小值，与 L 的最后一个元素进行比较，并决定是否需要将它们合并(如果重叠)或在 L 的末尾附加一个新的区间(如果它们不重叠)并继续处理，例如我们合并两个排序列表。

完成后，L 将是区间按 x 排序且不相交的并集。

对于交集，你可以做类似的事情。