3个间隔的重叠：最快的方法是什么

Question

给出 3 个区间 (a,b) , (c,d) , (e,f)，如果存在一个值 t ，那么最快的检测方法是什么（即有一个 yes/no 答案）同时a<=t<b AND c<=t<d AND e<=t<f ? 是否也可以计算出满足这个条件的t的范围，min(t),max(t) ?

此外，是否可以在不对订单进行任何假设的情况下做同样的事情？（即也可以是 b<a 或 a<b）

我找到了一个众所周知的两个细分市场解决方案，但三个细分市场并非易事。

欢迎使用任何 js 或 python 示例代码。

编辑：更正条件要求

Answer 1

Python 任意数量间隔的解决方案，无论间隔中数字的顺序如何。它会 return 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 是重叠范围的边界。

您知道是否有更快的解决方案需要更少的操作？

3个间隔的重叠：最快的方法是什么

overlapping of 3 intervals: what is the fastest way

javascript

python

logic

intervals

overlapping