Слияние интервалов

Слияние интервалов

Эта классическая задача на обработку массивов часто встречается на собеседованиях. Идея решения простая: если интервалы отсортированы, то пересекающиеся интервалы будут соседними. Это позволяет решить задачу за один проход линейной сложности.

Алгоритм

1. Сортируем интервалы по начальной точке
2. Инициализируем результат первым интервалом
3. Проходим по остальным интервалам:
   • Если начало текущего интервала ≤ конец последнего в результате → они пересекаются, расширяем конец
   • Иначе добавляем новый интервал в результат

Реализация

def merge_intervals(intervals):
    """Объединяет пересекающиеся интервалы.
    
    Args:
        intervals: List[List[int]] - список интервалов [start, end]
    
    Returns:
        List[List[int]] - объединённые интервалы
    """
    if not intervals:
        return []
    
    # Сортируем по началу интервала, затем по концу
    intervals.sort()
    
    # Инициализируем результат первым интервалом
    merged = [intervals[0]]
    
    # Проходим по остальным интервалам
    for current_start, current_end in intervals[1:]:
        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

Примеры работы

# Пример 1: есть пересечения
result = merge_intervals([[1,3], [2,6], [8,10], [15,18]])
print(result)  # [[1,6], [8,10], [15,18]]

# Пример 2: интервалы касаются
result = merge_intervals([[1,4], [4,5]])
print(result)  # [[1,5]]

# Пример 3: интервалы полностью содержатся
result = merge_intervals([[1,5], [2,3]])
print(result)  # [[1,5]]

Анализ сложности

• Временная сложность: O(n log n) - из-за сортировки, проход по элементам O(n)
• Пространственная сложность: O(n) или O(1) в зависимости от того, считаем ли выходной массив

Альтернативный подход: граничные события

Для очень больших диапазонов интервалов можно использовать подход с событиями (start/end), который работает за O(n) после сортировки:

def merge_intervals_events(intervals):
    """Альтернативный подход через события."""
    events = []
    for start, end in intervals:
        events.append((start, start))
        events.append((end, end))
    
    events.sort()
    
    merged = []
    count = 0
    start_point = None
    
    for point, event_type in events:
        if event_type == start:
            if count == 0:
                start_point = point
            count += 1
        else:  # end
            count -= 1
            if count == 0:
                merged.append([start_point, point])
    
    return merged

Ключевые моменты при интервью

• Сортировка - первый шаг для решения
• Граничные случаи: пустой список, один интервал, полностью содержащиеся интервалы
• Off-by-one ошибки: проверяй условие <= вместо < при сравнении начала и конца
• Модификация: можно ли модифицировать исходный массив или нужно новый?