Python:如何找到连接间隔开始和结束的最长连续间隔

Question

如何找到最长连接间隔链的长度？
例子:

[-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 中实现它。
提前致谢

Answer 1

动态规划:

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()))