需要一个算法，将网络块范围折叠成超集范围列表。

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。然而，每当插入新范围时，它可能是现有范围的超集，因此必须检查现有范围以查看它们是否可以折叠（例如从我的列表中删除）。

- Jen A

---

这些范围是否互不相交？如果不是，您希望算法如何处理重叠的范围，其中许多子范围可能是其中一部分？ - HenryR

你描述的“naive”算法有什么问题吗？在我看来似乎没什么问题... - Mike F

很好的问题！用户可以输入任何他们想要的范围，所以不能保证它们是不相交的。实际上，如果所有连续的范围都能合并成一个，那就太好了。 - Jen A

给MikeF：天真的方式可能会非常慢，如果我每次插入都必须与列表中的每个现有项目进行比较。我们有一些客户拥有超过40k个范围（并且希望添加更多！）。我不想做40k次比较来执行插入操作。 - Jen A

天真的方法也会像描述的那样无法处理两个范围重叠但没有一个完全包含另一个的情况。 - Dave Sherohman

Answer 1

这是一种线段并集计算方法。一个最优的算法（O(nlog(n)）的步骤如下：

2. 将所有端点（起始点和结束点）按顺序排序，放入列表L中（每个端点应该知道它所属的线段）。如果一个端点等于起始点，则认为起始点比终点小。
3. 从左到右依次遍历排好序的列表L，并维护数字LE-RE，其中LE是已经遍历过的左端点的数量，RE是已经遍历过的右端点的数量。
4. 每当LE-RE达到零时，你就到达了一个连通线段并集的末尾，你知道之前看到的线段并集（自上次返回0时）是一个超集。
5. 如果你还维护了每次归零之间的最小值和最大值，那么你就有了超集的边界。

最后，你会得到一个排序的不相交超集列表。但是，两个超集A和B可能是相邻的（A的端点恰好在B的起始点之前）。如果你想要合并A和B，可以通过简单的后处理步骤或者稍微修改第3步来实现：当LE-RE达到零时，只有当L中下一个元素不是当前元素的直接后继时，你才会将其视为超集的末尾。

- Camille

Answer 2

你知道你可以很容易地将IPv4地址转换为整数（int32数字），对吗？使用整数更加方便。因此，基本上每个地址都是在0到2^32范围内的一个数字。每个范围都有一个起始数字和一个结束数字。以下是您的示例：

1.1.1.1 to 2.2.2.5
1.1.1.2 to 2.2.2.4

可以写成：

16,843,009 to 33,686,021
16,843,010 to 33,686,020

因此，很容易看出一个范围是否在另一个范围内。如果满足以下条件，则一个范围完全在另一个范围内。

startIP2 >= startIP1 && startIP2 <= endIP1 &&
endIP1 >= startIP1 && endIP2 <= endIP1

在这种情况下，范围startIP2-endIP2完全包含在startIP1-endIP1的范围内。如果只有第一行是真的，则startIP2在startIP1-endIP1的范围内，但结束位置超出了该范围。如果只有第二行是真的，则endIP在范围内，但起始IP超出了范围。在这种情况下，如果只有一行是真的，则需要在开头或结尾扩展范围。如果两行都为假，则范围完全不相交，在这种情况下它们是两个完全独立的范围。

- Mecki

Answer 3

你需要做的就是检查范围是否重叠。如果两个范围重叠，则它们会合并成一个范围。当一个范围的右侧大于另一个范围的左侧时，这两个范围就会重叠。

- austirg

---

根据您的定义，10.1.1.0-10.2.2.255（一个范围）与4.4.4.0-4.4.4.255（另一个范围）重叠。 - tzot

Answer 4

好的，我的同事提出了这个答案，我认为它非常优秀。如果您发现任何问题，请告诉我：

• 按StartingIP对IP范围进行排序
• 对于要插入的每一行“x”：
  • 如果列表中有前一行“y”，则获取：
    • 如果x和y是连续的，则将y扩展到x的EndingIP
    • 否则，如果x.StartingIP <= y.StartingIP且x.EndingIP>y.EndingIP，则将y扩展到x.EndingIP
    • 否则，如果x是y的子集，则不执行任何操作
    • 否则，创建一个新范围
  • 否则，创建一个新范围并插入到列表中

- Jen A

---

是的，这样的东西肯定可以做到。 - Mike F

顺便说一句，似乎完全在一个列表上操作比从初始范围列表创建第二个列表更简单。 - Mike F