перекрытие 3 интервалов: что является самым быстрым способом

Question

Дайте 3 интервала (a, b), (c, d), (e, f), что является самым быстрым способом обнаружения (т.е. иметь ответ «да/нет») если существует значение t, которое в то же время a<=t<b AND c<=t<d AND e<=t<f ? Можно ли также вычислить диапазон t, который удовлетворяет этому условию, min(t),max(t)?

Кроме того, можно ли сделать то же самое без каких-либо гипотез о заказе? (т. е. может быть также b<a или a<b)

Я нашел хорошо известное решение для двух сегментов, но для трех не является тривиальным.

Любой код примера js или python приветствуется.

EDIT: исправлены требования состояние

Answer 1

решение Python для любого числа интервалов, независимо от порядка чисел в интервале. Он либо вернет True, min t value, max t value, либо False, t value, t value.

def in_interval(intervals): 
    if len(intervals) == 0: 
     return False, None, None 
    min_t = min(intervals[0]) 
    max_t = max(intervals[0]) 
    for interval in intervals[1:]: 
     min_t = max(min_t, min(interval)) 
     max_t = min(max_t, max(interval)) 
    if min_t > max_t: 
     return False, None, None 
    else: 
     return True, min_t, max_t 

Пробное:

>>> intervals = [(6,1),(2,20),(8,7)] 
>>> in_interval(intervals) 
(False, 1, 1) 
>>> intervals = [(6,1),(2,20),(4,9)] 
>>> in_interval(intervals) 
(True, 4, 6) 

Answer 2

def order(ab): 
    (a, b) = ab 
    if a is None or b is None: return None 
    if a>b: 
     return (b,a) 
    else: 
     return (a,b) 

def order2(ab, cd): 
    if ab is None or cd is None: return None 
    (a, b) = order(ab) 
    (c, d) = order(cd) 
    if a <= c: 
     return (ab, cd) 
    else: 
     return (cd, ab) 

def intersect(ab, cd): 
    if ab is None or cd is None: return None 
    ((a, b), (c,d)) = order2(ab, cd) 
    if b <= c: 
     return None 
    if d < b: 
     return (c, d) 
    else: 
     return (c, b) 

def intersect_of_three(ab, cd, ef): 
    return intesect(intersec(ab, cd), ef) 

Answer 3

мое первое решение для сортировки диапазона, чтобы иметь все интервалы в виде [x,y] с x<y. Тогда я вычислить

overlap_x=max(a,c,e) 
overlap_y=min(b,d,f) 

Полное перекрытие существует тогда и только тогда, когда

overlap_x<overlap_y 

где overlap_x и overlap_y являются границы перекрытия диапазона.

Знаете ли вы, есть ли более быстрое решение, требующее меньше операций?