Необходимо объединить диапазоны

Question

У меня есть список списков:

[[1, 2], [2, 3], [5, 8], [10, 11], [4, 6]]

Нужно сравнить элементы и при пересечении диапазонов сделать объединение, чтоб выбрались максимальные диапазоны.

На выходе должно получится:

[[1, 3], [4, 8], [10, 11]]

Answer 1

Добавляете первый элемент списка в новый список
Для остальных элементов пробегаетесь по новому списку и ищете не пересекается и этот диапазон с имеющимися
Если пересекается - объединяете с имеющимся
Если не пересекается - добавляете в новый список
Если в процессе обработки списка произошли объединения, то нужно будет с новым списком опять прогнать этот алгоритм, потому что могли появиться дополнительные объединения
Когда объединения заканчиваются, алгоритм заканчивается

О(n^2) плоховато (а то и O(n^3)), нужна оптимизация. Возможно, поможет сортировка списка отдельно по первым элементам и по вторым плюс "метод двух указателей" для их обхода, тут надо дальше думать.

Answer 2

Добавляете все концы диапазонов в список пар [значение, признак +1/-1 для начала или конца соответственно]

Сортируете список

Заводите счётчик активных диапазонов

Проходите по списку, добавляя к счётчику второе поле пары.

Если счётчик был 0, а стал 1, то начался новый объединённый диапазон, запоминаем начало

Если счётчик был 1, а стал 0, то закончился новый объединённый диапазон, добавляем его к результату

Сложность O(nlogn) из-за сортировки

Сортировка по умолчанию приводит к тому, что при одинаковом значении точка конца будет обрабатываться раньше точки начала, так что [0,1] и [1,2] не сольются. Если это требуется, то признак можно инвертировать (-1/+1), и при проходе отнимать его от счётчика.

Answer 3

def gen(lst):
    if len(lst) < 1:
        return
    if len(lst) < 2:
        yield lst[0]

    lst = sorted(lst, key=lambda x: (x[0], x[1]))  # сортируете список
    print(lst)
    x = lst[0][0]  # начальная точка 
    y = lst[0][1]  # конечная точка
    for i in lst[1:]:
        if i[0] <= y:  # если в следующем списке начало равно или меньше конца предыдущего
            y = i[1]   # заменяем конец
        else:
            yield [x, y]  # отдаем интервал
            x = i[0]      # переопределяем начало  и конец   
            y = i[1]

    yield [x,y]
    return

lst = [[1, 2], [2, 3], [5, 8], [10, 11], [4, 6]]

res = []
for i in gen(lst):
    res.append(i)
print(res)  #  [[1, 3], [4, 8], [10, 11]]

БЛОГ НА HUSL

Необходимо объединить диапазоны

Ответы (3 шт):