我正在开发一种编程语言，我想为其提供Range数据类型，目前不像通常那样是一个成对的列表int values (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)
where ||是并集并且&&是交集。
现在，如前所述，它们的实现只是一个列表。我知道存在更合适的数据结构（区间树），但现在我更关心从其他列表的并集/交集构建新列表。
实现这两个功能的最先进算法是什么？
提前致谢
由于您不想处理区间树而仅使用列表，因此我建议您将范围表示保留为按 x 坐标排序的不相交区间列表。
给定两个列表，您可以通过执行某种合并步骤来计算并集和交集，就像我们在合并排序列表中所做的那样。
Example:
对于 L1 和 L2 的并集：
创建 L 为空列表。
从 L1 和 L2 中取出 x 最小的区间，放到 L 上。
现在再次取最小的，与 L 的最后一个元素进行比较，并决定是否需要合并它们（如果重叠）或在 L 的末尾附加新的间隔（如果它们不重叠）并继续处理，就像我们在合并两个排序列表。
完成后，L 将是其间隔按 x 排序且不相交的并集。
对于交叉点，你可以做类似的事情。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
