python之找到图上点之间的最长公共(public)间隔

我得到以下输入:

[[['3', '7'], ['9', '17']], [['1', '5'], ['10', '20']], [['0', '6'], ['12', '19']]] 

每个子数组由一个或多个元素组成[['3', '7'], ['9', '17']] 表示这个函数1在x = 3 和 x = 7，相同的函数 1 也在 x = 9 和 x = 17 之间增长。 另一个function2在x=1和x=5之间增长，同一个function2在x=10和x=20之间增长。

这可以在这里以更好的格式化方式看到:

[['3', '7'], ['9', '17']] 
[['1', '5'], ['10', '20']] 
[['0', '6'], ['12', '19']] 

我需要找到一种方法来一起计算所有 3 个函数的最大增长间隔。在这种情况下，解是从 x = 12 到 x = 17，因为 17-12 = 5 比任何其他可能的组合都大。

另一个解决方案是 x =3 到 x =5，但由于不是最大的，所以这不是正确的解决方案

是否有 pythonic 方法来找到它？

直到现在我尝试针对这个特定案例计算它，但没有成功。

这是我得到的最简单的案例，而且它只是众多案例中的一个。 我的问题是我找不到比较子列表元素的正确方法，以便获得所有函数在同一时间间隔内增长的位置...

请您参考如下方法:

这是我能想到的最简洁的解决方案(有关此处发生的事情的解释，请参见下文):

from itertools import chain, groupby 
 
def get_longest_interval(x): 
    longest_interval = max( 
        ([v for _, v in grp] for k, grp in groupby(enumerate( 
            set.intersection(*(set(chain(*(range(int(start), int(end)+1) for (start, end) in f_intervals))) for f_intervals in x)) 
        ), lambda (index, num): index-num)), key=len 
    ) 
    return longest_interval[0], longest_interval[-1] 
 
x1 = [[['3', '7'], ['9', '17']], 
      [['1', '5'], ['10', '20']], 
      [['0', '6'], ['12', '19']]] 
 
x2 = [[[3, 7], [9, 21]], 
      [[1, 5], [10, 20]], 
      [[0, 6]]] 
 
for x in x1, x2: 
    print get_longest_interval(x) 
 
# This prints 
(12, 17) 
(3, 5) 

解释(一旦你创建了一些变量，所有这些都会变得更容易理解):

def get_longest_interval(x): 
    # Get available ranges for every function 
    function_ranges = [ 
        set( 
            # By chaining and unpacking them so (2 -> 4), (7 -> 9) becomes (2, 3, 4, 7, 8, 9) 
            chain(*(range(int(start), int(end)+1) for (start, end) in f_intervals)) 
        ) for f_intervals in x 
    ] 
    print "Function ranges", function_ranges 
 
    # Get the intersection of all the ranges: 
    #   This is the only place where everyone is increasing 
    valid_range = set.intersection(*function_ranges) 
    print "Valid range", valid_range 
 
    # Use python recipe to get groups of consecutive numbers using groupby 
    # https://docs.python.org/2.6/library/itertools.html#examples 
    # (3, 4, 5, 12, 13, 14, 15, 16, 17) -> ([3, 4, 5], [12, 13, 14, 15, 16, 17]) 
    # Then take the one that contains the most elements (max by length) 
    longest_interval = max( 
        ([v for _, v in grp] for k, grp in groupby(enumerate(valid_range), lambda (index, num): index-num)), key=len 
    ) 
    return longest_interval[0], longest_interval[-1] 
 
# This prints 
Function ranges [set([3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17]), set([1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]), set([0, 1, 2, 3, 4, 5, 6, 12, 13, 14, 15, 16, 17, 18, 19])] 
Valid range set([3, 4, 5, 12, 13, 14, 15, 16, 17]) 
(12, 17) 
Function ranges [set([3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]), set([1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]), set([0, 1, 2, 3, 4, 5, 6])] 
Valid range set([3, 4, 5]) 
(3, 5)