Найти самый длинный общий интервал между точками на графике

Question

Я дал следующий ввод:

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

Каждый суб-массив состоит из одного или нескольких элементов [['3', '7'], ['9', '17']] означает, что этот function1 растет между х = 3 и х = 7, эта же функция 1 также растет между x = 9 и x = 17. Другая функция2 растет между x = 1 и x = 5, и одна и та же функция2 растет между x = 10 и x = 20.

Это можно увидеть в более отформатированный пути здесь:

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

мне нужно найти способ, чтобы вычислить максимальный интервал роста всех 3-х функций вместе. В этом случае решение от x = 12 до x = 17, потому что 17-12 = 5 больше любой другой возможной комбинации.

другое решение х = 3 х = 5, но так как не максимальна, это не правильное решение

Есть вещий способ найти это?

До сих пор я пытался вычислить его для этого конкретного случая, без успеха.

Это самый простой случай, который я даю, и это только один случай из многих. Моя проблема в том, что я не могу найти правильный способ сравнить элемент подписок, чтобы получить, где все функции растут в одном интервале ...

Answer 1

Вот самое краткое решение, которое я мог придумать (для объяснения того, что происходит здесь, смотрите ниже):

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) 

Answer 2

Если есть только целые числа, вы можно использовать что-то вроде этого (работает с любым количеством функций и интервалов):

def full(bornes): 
    return [k for k in range(bornes[0], bornes[1] + 1)] 

li = [[[0, 8], [9, 17]], [[1, 8], [10, 20]], [[0, 8], [12, 19]]] 
li2 = [] 
for function in li: 
    li2.append([full(domain) for domain in function]) 

dict = {} 
for function in li2: 
    for domain in function: 
     for number in domain: 
      if not number in dict: 
       dict[number] = 1 
      else: 
       dict[number] += 1 

dict = {k:v for k,v in dict.iteritems() if v == len(li2)} 

x_longuest = None 
x_current = None 
current = 0 
longuest = 0 
for key in dict: 
    if key+1 in dict: 
     if current == 0: 
      x_current = key 
     current += 1 
    else: 
     if current > longuest: 
      longuest = current 
      x_longuest = x_current 
     current = 0 

if current > longuest: 
    longuest = current 
    x_longuest = x_current 

print(x_longuest, longuest) 

идея заключается в том, чтобы сделать словарь с определенными доменами, а затем сохранить только точки, где определены все функции, а затем проверить в словарь - самая длинная цепочка.

Answer 3

Позвольте мне набросать идею.

Сначала получите список всех возможных комбинаций.

listOfCombinations = list(itertools.product(function1, function2, function3)) 

Во-вторых, сверните этот список и возьмите максимум нижних границ и минимума верхних границ. Затем проверьте, является ли это самой большой разницей, которую вы обнаружили до сих пор.

for item in listOfCombinations: 
    val1 = max(item[0][0], item[1][0], item[2][0]) 
    val2 = min(item[0][1], item[1][1], item[2][1]) 
    range = val2 - val1 
    if range > maxRange: 
     maxRange = range 

Answer 4

если есть только целые числа, вы можете также использовать наборы для автоматического расчета перекрестки:

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

s1 = None 
s2 = None 

for f in array: 
    f1 = f[0] 
    f2 = f[1] 
    sf1 = set(xrange(int(f1[0]), int(f1[1])+1)) 
    sf2 = set(xrange(int(f2[0]), int(f2[1])+1)) 
    if not s1: 
     s1 = sf1 
     s2 = sf2 
    else: 
     s1.intersection_update(sf1) 
     s2.intersection_update(sf2) 

print s1, s2