在Python中找到重叠间隔之间的最长间隔？

Question

我有一个元组形式的间隔列表，如下所示：

data = [(5,10), (3,10), (13,15), (12,18), (20,29), (25,30)]

元组中的每个项目都有 2 个值（即开始、结束），不同间隔之间可能有也可能没有重叠。如果存在重叠的间隔，我只想取最长的间隔。此测试的输出如下：

output = [(3,10), (12,18), (20,29)]

如何使用标准库

numpy

或

pandas

在 Python 中执行此操作？

我开始做这样的天真事情，但我认为这不会很好地扩展......我也不想使用

NetworkX

import networkx as nx
data = [(5,10), (3,10), (13,15), (12,18), (20,29), (25,30)]

graph = nx.Graph()

n = len(data)
for i, a in enumerate(data):
    a_seq = set(range(a[0], a[1] + 1))
   
    for j in range(i+1, n):
        b = data[j]
        b_seq = set(range(b[0], b[1] + 1))

        n_overlap = len(a_seq & b_seq)
        if n_overlap:
            graph.add_edge(a, b, weight=n_overlap)

output = list()
for nodes in nx.connected_components(graph):
    lengths = dict()
    for node in nodes:
        start, end = node
        lengths[node] = end - start
    longest_interval, length_of_interval = sorted(lengths.items(), key=lambda x:x[1], reverse=True)[0]
    output.append(longest_interval)

我假设有更好的方法，但现在它正在逃避我。

编辑：任务中可能存在一些混乱，但我无法混合和匹配间隔（例如，（20,30）无效，因为它不是起始间隔之一）。

Answer 1

这实际上是图论的一个很好的例子，但是应该可以仅使用 numpy 通过从邻接矩阵开始实现您自己的算法。

邻接矩阵基本上为列表中的每个元素分配一个索引（显然只需使用列表索引），并为与其连接的每个元素分配一个

1

，为每个未连接的元素分配一个

0

，从而定义您的组在二维数组中。

经典的方法是实施深度优先搜索（此线程）[https://math.stackexchange.com/questions/277045/easiest-way-to-define-all-disconnected-sets-from-a- graph] 有一个很好的方法，使用拉普拉卡矩阵并查找特征值和特征向量（均在

numpy

中实现）