algorithm - 需要一种将网络 block 范围折叠成超集范围列表的算法

Question

我的数学让我失望了!我需要一种将网络范围缩小到超集的有效方法，例如如果我输入 IP 范围列表:

• 1.1.1.1 到 2.2.2.5
• 1.1.1.2 到 2.2.2.4
• 10.5.5.5 至 155.5.5.5
• 10.5.5.6 到 10.5.5.7

我想返回以下范围:

• 1.1.1.1 到 2.2.2.5
• 10.5.5.5 至 155.5.5.5

注意:输入列表没有排序(尽管它们可能是？)。执行此操作的简单方法是检查列表中的每个范围以查看输入范围 x 是否是子集，如果是，则不插入范围 x。但是，无论何时插入新范围，它都可能是现有范围的超集，因此您必须检查现有范围以查看它们是否可以折叠(例如，从我的列表中删除)。

Answer 1

这是段计算的联合。最佳算法(在 O(nlog(n)) 中)包括执行以下操作:

1. 对列表 L 中的所有端点(起点和终点)进行排序(每个端点都应该知道它所属的线段)。如果端点等于起点，则起点应被认为小于端点。
2. 从左到右遍历排序列表 L 并维护编号 LE-RE，其中 LE 是您已经通过的左端点的数量，并且RE 是您已经通过的正确终点的数量。
3. 每次 LE-RE 达到零时，您就处于连接的段并集的末尾，并且您知道您之前看到的段的并集(自上次返回零以来) 是一个超集。
4. 如果您还保持最小值和最大值，在每次归零之间，您就有超集的界限。

最后，您将获得一个已排序的不相交超集列表。尽管如此，两个超集 A 和 B 仍然可以相邻(A 的终点正好在 B 的起点之前)。如果你想合并 A 和 B，你可以通过一个简单的后处理步骤，或者通过稍微修改步骤 3 来完成:当 LE-RE 达到零时，你会认为这是一个结束仅当 L 中的下一个元素不是当前元素的直接后继时才进行超集。