How to find tuples that overlap a given range tuple

Question

Say I have a list full of tuples denoting a "from" and a "to" time: ``` tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ] ``` And I want to be able to retrieve a list of tuple that overlap with a given tuple: ``` searchTuple = (3,11) result = findOverlap(tuples, searchTuple) ``` This code should return the following list: ``` [ (0, 5), (5, 10), (10, 15) ] ``` While a searchTuple of (16, 22) should only return the last tuple (15,20) What is the most efficient way to code this retrieval? I tried various things but I am having trouble getting the algorithm to work properly. I figured the following different "overlaps" that I am interested in catching: ``` 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 overl…

Accepted Answer

Answering my own question because I found an elegant solution:

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

def overlap(tuples, search):
    res = []
    for t in tuples:
        if(t[1]>search[0] and t[0]<search[1]):
            res.append(t)
    return res

search = (1,11)
print overlap(tuples, search)
```

returns as expected:

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

How to find tuples that overlap a given range tuple

Solution

Problem