1

I have multiple lists containing tuples, e.g.,

list_A = [(start_1, end_1), (start_2, end_2), (start_3, end_3)]
list_B = [(start_4, end_4), ...]

Is there a smart way to go about generating a result_list that contains only the intersections, without having to search through each list in a nested fashion O(n^m)?

Example:

list_A = [('8:00 AM', '10:00 AM'), ('12:59 PM', '3:00 PM'), ('5:04 PM', '7:23 PM')]
list_B = [('9:06 AM', '9:47 AM'), ('9:51 AM', '12:45 PM'), ('1:33 PM', '2:52 PM'), ...]
list_C = [...]
list_D = [...]
# etc. etc. (m lists)

Please see the image below for an illustration of the problem: Intersection Problem

mkrieger1
  • 19,194
  • 5
  • 54
  • 65
Edwin Goh
  • 41
  • 5
  • Can you provide an *example*? are you dealing with integers? floats? what is the nature of you data?? – Binyamin Even Aug 27 '20 at 23:17
  • maybe you could do the same as your drawing does: create a 2D array (e.g. list of lists) with the tuples drawn out, and then check from the array the vertical columns the same way as we can do from the image visually? – antont Aug 27 '20 at 23:20
  • are you looking for the start and end inclusive ? or only start inclusive? – Akshay Sehgal Aug 27 '20 at 23:29
  • @BinyaminEven they're times - sorry for not including an example – Edwin Goh Aug 27 '20 at 23:35
  • Also https://stackoverflow.com/questions/303591/a-range-intersection-algorithm-better-than-on – mkrieger1 Aug 27 '20 at 23:36
  • 1
    @antont sounds like that might work, but my x axis is continuous, which makes discretization a tricky part of it – Edwin Goh Aug 27 '20 at 23:37
  • @AkshaySehgal they're timestamps, so I believe they should both be inclusive i.e., I would probably use `>=` and `<= ` for everything – Edwin Goh Aug 27 '20 at 23:38

1 Answers1

0

You can do the following in O(m*n) -

r = [[1,3], [5,7], [9,11]]
s = [[2,4], [5,6], [7,9], [11,14]]

r = [[i[0],i[1]+1] for i in r] #to make it inclusive at ends
s = [[i[0],i[1]+1] for i in s] #to make it inclusive at ends

overlapping_ranges = [set(range(*i[0])).intersection(set(range(*i[1]))) for i in list(itertools.product(r, s))]
overlapping_ranges = [i for i in overlapping_ranges if i] #removing nullsets

[{2, 3}, {5, 6}, {7}, {9}, {11}]
Akshay Sehgal
  • 18,741
  • 3
  • 21
  • 51