I'm looking for an idea to efficiently solve following problem:
I have a set of pairs of ranges (range = a pair of numbers), each range is unique (but has same size) e.g.
[ [(0,6),(34,40)], [(1,7),(35,41)], [(3,9),(12,18)], [(2,8),(36,42)], [(13,19),(22,28)], [(23,29),(14,20)] ]
Now I'd like to combine pairs of ranges, if ranges are overlapping e.g.
[(0,6),(34,40)] overlaps with [(1,7),(35,41)] -result-> [(0,7),(34,41)]
So as a result for above set I'd like to get (now each pair may have ranges of different size)
[ [(0,8),(34,42)], [(3,9),(12,18)], [(13,20),(22,29)] ]
The set might be pretty big, I'd like to avoid quadratic complexity if possible.
EDIT: My best idea so far (in Python) is below. I'd like to know if you know a better(faster) way. Also I'm not sure if my idea of removing already combined pairs is valid:
def ranges_overlap(range1, range2): return range1 < range2 and range2 < range1 def combine_pairs(pair1, pair2): return [(min(r1, r2), max(r1, r2)) for r1, r2 in zip(pair1, pair2)] def combine_overlapping_pairs(pairs): combined =  while pairs: pair1 = pairs.pop() already_combined =  for pair2 in pairs: for pair2_perm in itertools.permutations(pair2): does_overlap = True for range1, range2 in zip(pair1, pair2_perm): if not ranges_overlap(range1, range2): does_overlap = False break if does_overlap: pair1 = combine_pairs(pair1, pair2_perm) already_combined.append(pair2) break combined.append(pair1) # Not sure if I can do that for pair in already_combined: pairs.remove(pair) return combined