找到范围的最大交叉子集

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难的,因此实际上很难.对于近似/实际使用的建议将非常感谢!

更新2

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

~~看起来这是行的结束.对不起人!我将使用足够好的贪婪近似.谢谢.~~

如答案所述,我不认为该论文描述了这个问题......我们可能会根据范围提供更多信息.

Answer 1

如果我正确理解了问题,那么它不是您链接到的论文中描述的NP问题的实例.以下是我对该问题的理解,以及多项式时间解决方案.

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

将curOverlap和maxOverlap初始化为零.
遍历列表,为每个+递增curOverlap,并为每个递减 - .在每个增量上设置maxOverlap = max(curOverlap,maxOverlap).

要继续例如:
缬氨酸,CUR,最大
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.如果您想知道最大重叠发生的位置,您还可以存储与max关联的val.在这个例子中,这将给你20. 然后通过初始范围集找到包含20的5个范围是微不足道的.

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