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中实现。

提前致谢。

- Shahnawaz

---

这个问题可以视为在有向无环图中找到最长路径的问题来解决。参见 https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths 。该文章提到了寻找拓扑排序，但在这种情况下，这是非常简单的。只需要按照它们自然的顺序对端点进行排序即可。 - John Coleman

看一下这个链接：https://dev59.com/uF0b5IYBdhLWcg3wUP4X#29321323。它能回答你的问题吗？ - Roy2012

由于我在这里找不到既简单又高效的方法，所以我将使用递归回溯。 - Serge Ballesta

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

- Marat

Answer 2

稍微复杂一点的解决方案

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)

- fransua

Answer 3

这里是一种递归（回溯）的方法：

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

它按预期的方式运行：

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

- Serge Ballesta