Слияние перекрывающихся диапазонов

Условие

Дан массив диапазонов, представленных строками вида 'a-b', где a и b — целые числа (при этом a ≤ b). Нужно объединить все диапазоны, которые пересекаются или касаются друг друга, и вернуть новый массив диапазонов, упорядоченный по возрастанию начала.

Пример: ['2-4','7-10','3-5'] => ['2-5','7-10']

Ответ

Разберите строки в пары, отсортируйте по началу и расширяйте текущий интервал, пока следующий пересекается или имеет общую границу. Сложность определяется сортировкой: O(n log n).

import re

def merge_ranges(values):
    intervals = []
    for value in values:
        match = re.fullmatch(r'\s*(-?\d+)\s*-\s*(-?\d+)\s*', value)
        if not match:
            raise ValueError(value)
        left, right = map(int, match.groups())
        if left > right:
            raise ValueError(value)
        intervals.append((left, right))
    result = []
    for left, right in sorted(intervals):
        if result and left <= result[-1][1]:
            result[-1][1] = max(result[-1][1], right)
        else:
            result.append([left, right])
    return [f'{left}-{right}' for left, right in result]

Здесь «касаются» означает общую точку. Если требуется объединять соседние целочисленные отрезки 1–2 и 3–4, условие меняется на left <= end + 1.