Поздно, но может помочь кому-то, ищущему это. У меня была похожая проблема, но со словарями. Учитывая список временных диапазонов, я хотел найти перекрытия и объединить их, когда это возможно. Небольшая модификация ответа @samplebias привела меня к этому:

Функция слияния:

def merge_range(ranges: list, start_key: str, end_key: str):
    ranges = sorted(ranges, key=lambda x: x[start_key])
    saved = dict(ranges[0])

    for range_set in sorted(ranges, key=lambda x: x[start_key]):
        if range_set[start_key] <= saved[end_key]:
            saved[end_key] = max(saved[end_key], range_set[end_key])
        else:
            yield dict(saved)
            saved[start_key] = range_set[start_key]
            saved[end_key] = range_set[end_key]
    yield dict(saved)

Данные:

data = [
    {'start_time': '09:00:00', 'end_time': '11:30:00'},
    {'start_time': '15:00:00', 'end_time': '15:30:00'},
    {'start_time': '11:00:00', 'end_time': '14:30:00'},
    {'start_time': '09:30:00', 'end_time': '14:00:00'}
]

Исполнение:

print(list(merge_range(ranges=data, start_key='start_time', end_key='end_time')))

Вывод:

[
    {'start_time': '09:00:00', 'end_time': '14:30:00'},
    {'start_time': '15:00:00', 'end_time': '15:30:00'}
]

Часть сортировки: используйте стандартную сортировку, она правильно сравнивает кортежи.

sorted_tuples = sorted(initial_ranges)

Часть слияния. Это также устраняет дублирующиеся диапазоны, поэтому нет необходимости в set. Предположим, у вас есть current_tuple и next_tuple.

c_start, c_end = current_tuple
n_start, n_end = next_tuple
if n_start <= c_end: 
  merged_tuple = min(c_start, n_start), max(c_end, n_end)

Надеюсь, логика достаточно ясна.

Для просмотра следующего кортежа вы можете использовать индексированный доступ к sorted tuples; в любом случае, это полностью известная последовательность.

Сортируйте все границы, затем возьмите все пары, у которых за концом границы следует начало границы.

def mergeOverlapping(initialranges):
    def allBoundaries():
        for r in initialranges:
            yield r[0], True
            yield r[1], False

    def getBoundaries(boundaries):
        yield boundaries[0][0]
        for i in range(1, len(boundaries) - 1):
            if not boundaries[i][1] and boundaries[i + 1][1]:
                yield boundaries[i][0]
                yield boundaries[i + 1][0]
        yield boundaries[-1][0]

    return getBoundaries(sorted(allBoundaries()))

Хм, не так красиво, но по крайней мере было весело писать!

РЕДАКТИРОВАТЬ: Спустя годы, после взрыва, я понял, что мой код был неправильным! Это новая версия просто для удовольствия:

def mergeOverlapping(initialRanges):
    def allBoundaries():
        for r in initialRanges:
            yield r[0], -1
            yield r[1], 1

    def getBoundaries(boundaries):
        openrange = 0
        for value, boundary in boundaries:
            if not openrange:
                yield value
            openrange += boundary
            if not openrange:
                yield value

    def outputAsRanges(b):
        while b:
            yield (b.next(), b.next())

    return outputAsRanges(getBoundaries(sorted(allBoundaries())))

По сути, я отмечаю границы с помощью -1 или 1, а затем сортирую их по значению и выводу только тогда, когда баланс между открытыми и закрытыми скобками равен нулю.

Сортировать кортежи, затем перечислить, если t1.right> = t2.left => объединить и перезапустить с новым списком, ...

->

def f(l, sort = True):
    if sort:
        sl = sorted(tuple(sorted(i)) for i in l)
    else:
        sl = l
    if len(sl) > 1:
        if sl[0][1] >= sl[1][0]:
            sl[0] = (sl[0][0], sl[1][1])
            del sl[1]
            if len(sl) < len(l):
                return f(sl, False)
    return sl