algorithm - 找到范围的最大相交子集

Question

如果你有一组范围，比如下面这个简单的例子......

[
    [12, 25], #1
    [14, 27], #2
    [15, 22], #3
    [17, 21], #4
    [20, 65], #5
    [62, 70], #6
    [64, 80]  #7
]

...您如何计算最大相交子集(不太确定如何表达它，但我的意思是“相交并具有最高基数的范围子集”)并确定交叉度(该子集中范围的基数)？

从逻辑上讲，我可以解决这个问题，并且可以将其转化为一个朴素的算法。沿着列表往下看，我们看到 1-5 相交，5-7 相交，#5 与两组相交。

我想要的结果只是子集，因为它提供了有关基数的信息，而且只要它们全部相交，我就可以轻松计算出集合的交集。在上面的示例中，它将是 [[14, 27],[15, 22],[12, 25],[17, 21],[20, 65]] .

在我的脑海中，我可能会尝试将每个范围转换为一个图形节点，连接相交的节点，并找到最大的完全连接的图形。

我也在反复考虑从头开始，继续构建一个相交范围列表，每个范围都有一个运行交集以进行检查——直到你遇到一个不相交的元素，然后开始一个新列表。继续根据现有交叉点检查每个项目。但是我不确定这是否完整。

我可以尝试实现一些东西(lang 是 ruby​​ FWIW)，但我很想听听其他人如何解决这个问题，以及最有效和优雅的方法是什么。

更新:

我相信这是最大团问题的一个特例，它是 NP-hard，因此实际上很困难。非常感谢有关近似值/实际使用的建议!

另请参阅:http://en.wikipedia.org/wiki/Maximum_clique/Find all complete sub-graphs within a graph

更新 2

在这里找到了这个问题的 NP-hardness 和 NP-completeness 的一个很好的证明: http://www.cs.bris.ac.uk/~popa/ipl.pdf

<罢工>

看来这行到此结束了。对不起各位!我将使用足够好的贪婪近似值。谢谢。

如答案中所述，我认为该论文没有描述这个问题......我们可能会根据范围在此处提供更多信息。

Answer 1

如果我对问题的理解正确，则它不是您链接到的论文中描述的 NP 问题的实例。这是我对问题的理解，以及多项式时间的解决方案。

1. 给定一组有限的实数范围，例如 n:[A₁, B₁]， [A₂, B₂], ..., [A_n, B_n], 其中 A _i ≤ B_i.

2. 创建起点和终点的排序列表，按数字排序，指示该点是起点还是终点。

在您的示例中，这将是:12+、14+、15+、17+、20+、21-、22-、25-、27-、62+、64+、65-、70-、 80-

1. 将curOverlap 和maxOverlap 初始化为零。

2. 遍历列表，为每个 + 递增 curOverlap，为每个 - 递减。在每个增量上设置 maxOverlap = max(curOverlap, maxOverlap)。

继续你的例子:
值、电流、最大值
12, 1, 1
14, 2, 2
15, 3, 3
17, 4, 4
20, 5, 5
21, 4, 5
22, 3, 5
25, 2, 5
27, 1, 5
62, 2, 5
64, 3, 5
65, 2, 5
70, 1, 5
80, 0, 5

最大重叠为 5。如果您想知道最大重叠发生的位置，您也可以存储与最大值关联的 val。这会给你 20. 在这个例子中。然后，遍历初始范围集并找到包含 20 的 5 个范围就很简单了。

-edit- 如果您有重复的值，请在每个值的减号之前计算加号，以便包括在单个点重叠的范围。