时间戳

首页 > 解决方案 > Python：如何找到具有连接间隔开始和结束的最长连续间隔

python - Python：如何找到具有连接间隔开始和结束的最长连续间隔

问题描述

如何找到最长连接区间链的长度？

例子：

[-4,1][1,5][2,10][3,5][1,3][3,8][8,12][5,11]

这里最长的链是：

[-4,1][1,3][3,8][8,12]

如您所见，当前间隔的结束应该是下一个间隔的开始。我想从某种意义上找到最长链的长度：length=(12-(-4))=16

我认为这涉及递归？但我不知道如何在 Python 中实现它。

提前致谢

标签： python

解决方案

动态规划：

from collections import defaultdict

intervals = [-4,1][1,5][2,10][3,5][1,3][3,8][8,12][5,11]
intervals = sorted(intervals, key=lambda x: (x[1], x[0]))  # will sort by end, then start

distances = defaultdict(int)
for start, end in intervals:
    # this is the key step: at each point, the max length interval up to here
    # is max combined length of all intervals that end here
    distances[end] = max(distances[end], distances[start] + end-start)
print(max(distances.values()))

推荐阅读