algorithm - python smallest range from multiple lists -

i need find smallest range group of integer lists using @ least 1 element each list.

list1=[228, 240, 254, 301, 391] list2=[212, 345, 395] list3=[15, 84, 93, 103, 216, 398, 407, 488] 

in example smallest range [391:398], because covers values 391, 395 , 398 3 lists.

each list have @ least 1 value , there many more lists

what quickest computationally way find range?

since input lists sorted, can use merge sort , need test range whenever next value being merged in came different list last. track last value you've seen on each of lists, , calculate ranges between lowest value , current. o(n) linear time approach, n total number of elements of input lists.

the following implements approach:

def smallest_range(*lists):     iterables = [iter(it) in lists]     iterable_map = {}     key, in enumerate(iterables):         try:             iterable_map[key] = [next(it), key, it]         except stopiteration:             # empty list, won't able find range             return none     lastvalues, lastkey = {}, none     candidate, candidatediff = none, float('inf')      while iterable_map:         # next value in merge sort         value, key, = min(iterable_map.values())         lastvalues[key] = value          if len(lastvalues) == len(lists) , lastkey != key:             minv = min(lastvalues.values())             difference = value - minv             if candidatediff > difference:                 candidate, candidatediff = (minv, value), difference         lastkey = key          try:             iterable_map[key][0] = next(it)         except stopiteration:             # iterable empty, remove consideration             del iterable_map[key]      return candidate 

demo:

>>> list1 = [228, 240, 254, 301, 391] >>> list2 = [212, 345, 395] >>> list3 = [15, 84, 93, 103, 216, 398, 407, 488] >>> smallest_range(list1, list2, list3) (391, 398)