python - 如何找到与给定范围元组重叠的元组

Question

假设我有一个包含表示“从”和“到”时间的元组的列表:

tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]

我希望能够检索与给定元组重叠的元组列表:

searchTuple = (3,11)
result = findOverlap(tuples, searchTuple)

此代码应返回以下列表:

[ (0, 5), (5, 10), (10, 15) ]

虽然 (16, 22) 的搜索元组应该只返回最后一个元组 (15,20)

对这种检索进行编码的最有效方法是什么？我尝试了各种方法，但我无法让算法正常工作。我想出了以下我有兴趣捕捉的不同“重叠”:

a) tuple_min < find_min AND tuple_max > find_max

search tuple -> |         | 
            |----------------| the search tuple is entirely contained

b) tuple_min > find_min AND tuple_max > find_max

         |         |
            |----------------| the left part of the tuple overlaps

c) tuple_min < find_min AND tuple_max < find_max

              |         |
    |----------------| the right part of the tuple overlaps

但是，我实现此方法后得到的结果最终给了我错误的结果……我的想法错在哪里？

Answer 1

您还没有涵盖搜索元组完全包含与其进行比较的当前元组的情况。在你的情况下，说 (3,11) 反对 (5,10)