Finding longest overlapping ranges [duplicate]

Question

I have ranges in a list like:

ranges = [(1, 50), (49, 70), (75, 85), (84, 88), (87, 92)] 

I would like to find the longest ranges that can be constructed from these (when they overlap with each other).

Expected output:

[(1, 70), (75, 92)] 

I have a solution, however it is way too complicated, and I am sure there must be an easier solution to this problem

My solution:

def overlap(x, y):     return range(max(x[0], y[0]), min(x[-1], y[-1]) + 1)  ranges = [(1, 50), (49, 70), (75, 85), (84, 88), (87, 92)]  beg, end = min([x[0] for x in ranges]), 0 for i in ranges:     if i[0] == beg:         end = i[1] while beg:     for _ in ranges:         for i in ranges:             if i[1] > end and overlap(i, [beg, end]):                 end = i[1]     print(beg, end)     try:         beg = min([x[0] for x in ranges if x[0] > end])         for i in ranges:             if i[0] == beg:                 end = i[1]     except ValueError:         beg = None 

Output:

1 70 75 92 

Answer 1

I think you can sort your input by the start of the ranges, then iterate through them. At each item, it is either added to the current range (if the start is less than the end of the current range) or we yield out current range and begin accumulating a new range:

def overlaps(ranges):     ranges = sorted(ranges)  # If our inputs are garunteed sorted, we can skip this     it = iter(ranges)     try:         curr_start, curr_stop = next(it)         # overlaps = False  # If we want to exclude output ranges not produced by overlapping input ranges     except StopIteration:         return     for start, stop in it:         if curr_start <= start <= curr_stop:  # Assumes intervals are closed             curr_stop = max(curr_stop, stop)             # overlaps = True         else:             # if overlaps:             yield curr_start, curr_stop             curr_start, curr_stop = start, stop             # overlaps = False     # if overlaps:     yield curr_start, curr_stop  print(list(overlaps([(1, 50), (49, 70), (75, 85), (84, 88), (87, 92)]))) # [(1, 70), (75, 92)]  print(list(overlaps([(20, 30), (5, 10), (1, 7), (12, 21)]))) # [(1, 10), (12, 30)]