寻找与给定区间有非空交集的区间。

Question

问题如下：我有一个列表 intervals，它由形如 (start，end) 的元组组成 [其中 start <= end]。每个元组表示一个区间（实线上的），我们假设 intervals 中的区间彼此不重叠。给定一个新区间 (s,e)，我想编写一个 Python 函数，检查 (s, e) 是否与 intervals 中的任何区间重叠。如果 (s, e) 与 intervals 中的至少一个区间存在非空交集，则该函数应返回列表 intervals 中这些区间的索引。

假设函数名为 find_intersections。那么，给定 intervals = [(1, 3.5), (5.5, 8.7), (10.2, 22.6), (22.7, 23.1)]，期望的输出结果将是：

- find_intersection(intervals, (3.2, 5.)) 返回 array([0]) - find_intersection(intervals, (6.1, 7.3)) 返回 array([1]) - find_intersection(intervals, (9.1, 10.2)) 返回 No intersection. - find_intersection(intervals, (5.8, 22.9)) 返回 array([1, 2, 3])。

我编写了 find_intersection 的代码：

import itertools

def find_intersection(intervals, new_interval):
    _times = sorted(list(itertools.chain.from_iterable(intervals)))
    ind = np.searchsorted(_times, np.asarray(new_interval))
    parity = np.mod(ind, 2)
    if (not np.any(parity)) and ind[1] == ind[0]:
        print('No intersection.')
    elif parity[0] == 1:
        ub = ind[1] if parity[1] == 1 else ind[1] - 1
        return np.arange((ind[0] - 1) / 2, (ub - 1) / 2 + 1)
    elif parity[1] == 1:
        lb = ind[0] if parity[0] == 1 else ind[0] + 1
        return np.arange((lb - 1) / 2, (ind[1] - 1) / 2 + 1)
    else:
        lb = ind[0] if parity[0] == 1 else ind[0] + 1
        ub = ind[1] if parity[1] == 1 else ind[1] - 1
        return np.arange((lb - 1) / 2, (ub - 1) / 2 + 1)

我认为这段代码能够完成任务。

是否有更简单/更聪明的方法来解决这个问题？

- pitchounet

---

在Code Review上交叉发布并回答：https://codereview.stackexchange.com/q/203468/31562 - Simon Forsberg

Answer 1

intervals = [(1, 3.5), (5.5, 8.7), (10.2, 22.6), (22.7, 23.1)]


def find_intersection(intervals, new_interval):
    start, end = new_interval

    return (i for i, (a, b) in enumerate(intervals)
        if (a < start < b) or (a < end < b) or (a > start and b < end))


candidates = ((3.2, 5.), (6.1, 7.3), (9.1, 10.2), (5.8, 22.9))
for c in candidates:
    print(c, "->", list(find_intersection(intervals, c)))

- user3278460

Answer 2

列表中的第i个区间重叠，当且仅当

start[i] < e and s < end[i].

所以，按照递增的start值对区间进行排序，然后扫描列表，直到找到第一个end[i] > s并继续只要start[i] < e。在进行过程中保留索引。

这需要O（N Log N）进行排序，然后是Θ（N）最坏情况下的搜索。

---

如果允许排序并且有许多(s,e)区间要尝试，则通过在start[i]和end[i]值之间进行二分搜索来查找第一个和最后一个i可能很有用，而不是通过线性搜索。这将把成本从Θ（M + K）降低到Θ（Log N），其中M是第一个重叠的平均索引（通常M = O（N）），K是重叠的平均数量。

---

如果不允许排序，则需要依次测试每个间隔以检测重叠，使用上述条件。成本Θ（N）。

- user1196549

Answer 3

两个区间相交，如果：

def intersect(i1, i2):
    return max(i1[0], i2[0]) < min(i1[1], i2[1])

所以，只是一个列表推导式

def find intersection(intervals, i2):
    return [i1 for i1 in intervals if intersect(i1, i2)]

- blue_note

Answer 4

您可以使用区间树包，它提供了内置函数，返回多个类似的查询。不幸的是，似乎没有返回重叠区间索引的函数，只有区间本身。例如：

import IntervalTree

intervals = [(1, 3.5), (5.5, 8.7), (10.2, 22.6), (22.7, 23.1)]
tree = IntervalTree.from_tuples(intervals)

tree.search(3.2, 5.) % ~~>   {Interval(1, 3.5)}
tree.search(9.1, 10.2) % ~~> set()
tree.search(5.8, 22.9) % ~~> {Interval(5.5, 8.7), Interval(10.2, 22.6), Interval(22.7, 23.1)}
tree[5.8:22.9] % ~~>         same as above

一旦您获得所需的区间集，就可以轻松返回它们的索引：

[intervals.index((tr.begin, tr.end)) for tr in tree[5.8:22.9]]

如果区间列表很大，您可能希望使用字典进行查找索引，因为对于列表长度而言，.index方法需要线性时间。尽管仅为解决此问题而安装软件包可能是一种负担，但如果您正在处理区间，则使用区间树数据结构并利用软件包中编写的优化方法可能是值得的。为了获得更好的性能，您还可以检查ncls软件包，尽管其文档和方法似乎有限。希望这可以帮助您。

- Ioannis