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

overlapping of 3 intervals: what is the fastest way

本文关键字：方法 什么 重叠 3个      更新时间：2023-09-26

给出 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 示例代码。

编辑：更正的条件要求

适用于任意间隔数的 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)

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)

我的第一个解决方案是对范围进行排序，以便所有间隔的形式都与x<y [x,y]。然后我计算 

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

完全重叠存在当且仅当 

overlap_x<overlap_y

其中overlap_x和overlap_y是重叠范围的边界。

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

相关文章：