Finding longest overlapping ranges [duplicate]

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_stopprint(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)]

you can use zip to group all the start values and end values of each range pair. If the start value is lower than the previous end value then there is an overlap so remove that start and end value. we are using an int to track which index in each low and high list we are looking the low index is always one higher than the high index.

#split the numbers in to the low and high part of each range#and set the index position for each of themranges = [(1, 50), (49, 70), (75, 85), (84, 88), (87, 92)]low, high = [list(nums) for nums in zip(*ranges)] l, h = 1, 0#Iterate over the ranges and remove when there is an overlap if no over lap move the pointerswhile l < len(low) and h < len(high):    if low[l] < high[h]:        del low[l]        del high[h]    else:        l +=1        h +=1#zip the low and high back into rangesnew_ranges = list(zip(low, high))print(new_ranges)

OUTPUT

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

Could be done using functools.reduce:

from functools import reduceranges = [(1, 50), (45, 47), (49, 70), (75, 85), (84, 88), (87, 92)]reducer = (    lambda acc, el: acc[:-1:] + [(min(*acc[-1], *el), max(*acc[-1], *el))]    if acc[-1][1] > el[0]    else acc + [el])print(reduce(reducer, ranges[1::], [ranges[0]]))

Gives:

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

Hard to put into words, but it uses reduce to go through the ranges. If the last tuple in the range and the next provided overlap (if acc[-1][1] > el[0]), it creates a new range from the (min, max) of both and then replaces this new combined range to what was behind it (acc[:-1:] + [(min, max)]), otherwise simply adding the new range to the end (acc + [el]).

Edit: After reviewing other answers, updated to take min/max of the two ranges compared instead of just first and last