Python: How to find longest continuous interval with connected interval start and end

Question

How can I find the length of the longest connected interval chain?

Example:

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

Here the longest chain would be:

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

As you can see, the end of the current interval should be the start of the next interval. I would like to find the length of the longest chain in the sense: length=(12-(-4))=16

I think this involves recursion? But I don't know how to implement it in Python.

Thanks in advance

Answer 1

Dynamic programming:

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