如果您有一组范围，例如下面的简单示例…

[
    [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]]。

我可能会尝试将每个范围转换为一个图形节点，将相交的部分连接起来，然后找到最大的全连接图。

我还反复考虑要从头开始，继续建立相交范围的列表，并在每个相交范围上运行一个相交的区域以进​​行检查-
直到您找到一个不相交的元素，然后开始一个新列表。继续对照现有交叉口检查每个项目。但是我不确定这是否完成。

我可以尝试实现某些东西（语言是ruby FWIW），但是我很想听听其他人如何解决这个问题，以及最有效，最优雅的方法是什么。

更新：

我认为这是最大派系问题的一个具体案例，这是NP难题，因此实际上很困难。对于近似值/实际使用的建议将不胜感激！

另请参阅：http :
//en.wikipedia.org/wiki/Maximum_clique
/ 查找图中的所有完整子图

更新2

在此找到了有关此问题的NP硬度和NP完整性的很好证明： http :
//www.cs.bris.ac.uk/~popa/ipl.pdf

看起来这是行的结尾。抱歉！我将使用足够好的贪婪近似进行工作。谢谢。

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