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

The problem can be solved by thinking of it as that of finding the longest path in a directed acyclic graph. See https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths . That article refers to finding a topological sorting, but in this case that is utterly trivial. Just sort the endpoints in their natural order. — John Coleman, Jul 27 '20 at 14:10
Have a look at this: https://stackoverflow.com/questions/29320556/finding-longest-path-in-a-graph/29321323. Does it answer your question? — Roy2012, Jul 27 '20 at 14:32
As I cannot find both reasonably simple yet efficient methods here, I would just use a recursive [backtracking](https://en.wikipedia.org/wiki/Backtracking) — Serge Ballesta, Jul 27 '20 at 14:32

Marat · Accepted Answer · 2020-07-27T14:34:46.593

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

score 0 · Answer 2 · answered Jul 27 '20 at 15:40

A bit more complex solution

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

# we create a simple tree structure
tree = {}
for v2 in example:
    tree[tuple(v2)] = ([v3 for v3 in example if v3[0] == v2[1]], 
                       [v3 for v3 in example if v3[1] == v2[0]])

def is_ancestor(n1, n2, tree):
    """check if a node is ancestral to another"""
    if n1 in tree[tuple(n2)][1]:
        return True
    for n3 in tree[tuple(n2)][1]:
        return is_ancestor(n1, n3, tree)
    return False

def get_longest(example, tree, result=None, v=None):
    """searches for longest path"""
    if not result:
        result = [[v]]
    for desc in tree[tuple(v)][0]:
        if result[-1][-1] not in tree[tuple(desc)][1]:
            result.append([r for r in result[-1] 
                           if is_ancestor(r, desc, tree)])
        result[-1].append(desc)
        get_longest(example, tree, result, desc)
    return result

# check from each starting point
max_dist = 0
for n in example:
    for intervals in get_longest(example, tree, [], n):
        print (intervals, intervals[-1][1] , intervals[0][0])
        dist = intervals[-1][1] - intervals[0][0]
        if dist > max_dist:
            max_dist = dist
print(max_dist)

score 0 · Answer 3 · answered Jul 27 '20 at 16:03

Here is a recursive (backtracking) way:

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

def longest(lst):
    mx = (0, [])
    for i in range(1, len(lst) -1):    # test for all following and acceptable elements
        if lst[i][0] == lst[0][1]:
            add = longest(lst[i:])
            if add[0] > mx[0]:         # keep "longest" chain 
                mx = add
    #print(lst, mx)
    return (lst[0][1] - lst[0][0] + mx[0], [lst[0]] + mx[1])

# chain elements must be in increasing order
print(longest(sorted(lst)))

It gives as expected:

(15, [[-4, 1], [1, 3], [3, 5], [5, 11]])

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

3 Answers3