Объединение интервалов

Решение

Понимание задачи

Объединить интервалы, которые пересекаются или соприкасаются. Например:

• [1,3] и [2,6] пересекаются -> [1,6]
• [1,5] и [5,10] соприкасаются -> [1,10]
• [1,5] и [7,10] не пересекаются -> оставить как есть

Оптимальный алгоритм: Sort + Merge

def merge_intervals(intervals):
    """
    Объединяет пересекающиеся интервалы.
    """
    if not intervals:
        return []
    
    # Сортируем по началу интервала
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        # Если текущий пересекается с последним
        if current[0] <= last[1]:
            # Объединяем: расширяем конец
            merged[-1] = [last[0], max(last[1], current[1])]
        else:
            # Не пересекается: добавляем как новый
            merged.append(current)
    
    return merged

Как это работает

Пример: [[1,3], [2,6], [8,10], [15,18]]

Шаг 1: Сортировка по началу (уже отсортировано) Шаг 2: merged = [[1, 3]] Шаг 3: Обработка [2, 6]

• 2 <= 3 (пересекается)
• Объединяем: [1, max(3, 6)] = [1, 6]
• merged = [[1, 6]] Шаг 4: Обработка [8, 10]
• 8 > 6 (не пересекается)
• Добавляем: merged = [[1, 6], [8, 10]] Шаг 5: Обработка [15, 18]
• 15 > 10 (не пересекается)
• Добавляем: merged = [[1, 6], [8, 10], [15, 18]]

Результат: [[1, 6], [8, 10], [15, 18]]

Сложность

• Временная: O(n log n) — сортировка O(n log n) + проход O(n)
• Пространственная: O(1) или O(n) — зависит от требования (место для результата)

Расширенная версия с обработкой ошибок

def merge_intervals_advanced(intervals):
    """
    Объединяет интервалы с обработкой граничных случаев.
    """
    # Пустой список
    if not intervals:
        return []
    
    # Валидация входных данных
    for interval in intervals:
        if not isinstance(interval, (list, tuple)) or len(interval) != 2:
            raise ValueError("Каждый интервал должен быть парой [start, end]")
        if interval[0] > interval[1]:
            raise ValueError("Start не может быть больше end")
    
    # Сортируем по началу, затем по концу
    intervals.sort(key=lambda x: (x[0], x[1]))
    
    merged = [list(intervals[0])]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        if current[0] <= last[1]:
            # Объединяем интервалы
            merged[-1][1] = max(last[1], current[1])
        else:
            # Новый интервал
            merged.append(list(current))
    
    return merged

Тестирование

# Базовые случаи
assert merge_intervals([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
assert merge_intervals([[1,4],[4,5]]) == [[1,5]]
assert merge_intervals([[1,2],[3,4]]) == [[1,2],[3,4]]

# Пересекающиеся интервалы
assert merge_intervals([[1,5],[2,3]]) == [[1,5]]
assert merge_intervals([[1,4],[2,3]]) == [[1,4]]

# Вложенные интервалы
assert merge_intervals([[1,10],[2,3],[4,5],[6,7]]) == [[1,10]]

# Один интервал
assert merge_intervals([[1,5]]) == [[1,5]]

# Пустой список
assert merge_intervals([]) == []

# Несортированные
assert merge_intervals([[3,4],[1,2],[5,6]]) == [[1,2],[3,4],[5,6]]

# Соприкасающиеся
assert merge_intervals([[1,4],[4,5]]) == [[1,5]]

Альтернативные подходы

Способ 1: С кучей (Priority Queue)

import heapq

def merge_intervals_heap(intervals):
    if not intervals:
        return []
    
    # Используем минимальную кучу
    heap = [[end, start] for start, end in intervals]
    heapq.heapify(heap)
    
    merged = [[heapq.heappop(heap)[1], heapq.heappop(heap)[0]]]
    
    while heap:
        current_end, current_start = heapq.heappop(heap)
        last_start, last_end = merged[-1]
        
        if current_start <= last_end:
            merged[-1][1] = max(last_end, current_end)
        else:
            merged.append([current_start, current_end])
    
    return merged

• O(n log n) время
• O(n) память
• Более сложно

Способ 2: С использованием координат (Sweep Line)

def merge_intervals_sweep(intervals):
    if not intervals:
        return []
    
    events = []
    for start, end in intervals:
        events.append((start, 0))  # 0 для начала
        events.append((end, 1))    # 1 для конца
    
    events.sort()
    merged = []
    count = 0
    start = 0
    
    for pos, event_type in events:
        if event_type == 0:
            if count == 0:
                start = pos
            count += 1
        else:
            count -= 1
            if count == 0:
                merged.append([start, pos])
    
    return merged

• O(n log n) время
• Более сложный алгоритм

Граничные случаи

# Пустой список
assert merge_intervals([]) == []

# Один интервал
assert merge_intervals([[1,5]]) == [[1,5]]

# Все вложены
assert merge_intervals([[1,100],[2,3],[4,5]]) == [[1,100]]

# Не пересекаются
assert merge_intervals([[1,2],[3,4],[5,6]]) == [[1,2],[3,4],[5,6]]

# Идентичные интервалы
assert merge_intervals([[1,5],[1,5],[1,5]]) == [[1,5]]

# Соприкасаются по границам
assert merge_intervals([[1,3],[3,5]]) == [[1,5]]
assert merge_intervals([[1,3],[4,5]]) == [[1,3],[4,5]]

# Большой диапазон
assert merge_intervals([[0,1000000],[1,5]]) == [[0,1000000]]

Выводы

• Sort + Merge — оптимальное решение
• O(n log n) время — доминирует сортировка
• O(1) доп. память — если не считать результата
• Ключевой момент: после сортировки можно эффективно объединять
• Для QA: проверить все типы пересечений, граничные случаи, несортированные входы