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

我的数学功能让我失望!我需要一种将网络范围减少到超集的有效方法,例如,如果我输入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.但是,无论何时插入新范围,它都可能是现有范围的超集,因此您必须检查现有范围以查看它们是否可以折叠(例如,从我的列表中删除).

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

对列表L中的所有端点(起始点和结束点)进行排序(每个端点应该知道它所属的段).如果端点等于起点,则应将起点视为小于enpoint.

从左到右遍历排序列表L并保持数字LE-RE,其中LE是您已经通过的左端点数,RE是您已经传递的右端点数.

每当LE-RE达到零时,你就处于一个连接的段连接的末尾,你知道你之前看到的段的并集(从前一个返回到零)是一个超集.

如果你还保持最小值和最大值,每次返回零之间,你就有超集的界限.

最后,您将获得不相交的超集的排序列表.两个超集A和B可以相邻(A的端点恰好在B的起点之前).如果你想要合并A和B,你可以通过一个简单的后处理步骤,或者通过稍微修改第3步来做到这一点:当LE-RE达到零时,你会认为它只是一个超集的结尾,只有下一个元素在L不是当前元素的直接继承者.