PrepBro
← Назад к вопросам

Merge Intervals

2.0 Middle🔥 191 комментариев
#Коллекции и структуры данных#Язык Swift

Условие

Дан массив интервалов intervals, где intervals[i] = [start_i, end_i]. Объедините все пересекающиеся интервалы и верните массив непересекающихся интервалов, которые покрывают все интервалы входных данных.

Примеры:

Пример 1:

  • Вход: intervals = [[1,3], [2,6], [8,10], [15,18]]
  • Выход: [[1,6], [8,10], [15,18]]
  • Объяснение: Интервалы [1,3] и [2,6] пересекаются, объединяем в [1,6]

Пример 2:

  • Вход: intervals = [[1,4], [4,5]]
  • Выход: [[1,5]]
  • Объяснение: Интервалы [1,4] и [4,5] считаются пересекающимися

Ограничения:

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

Подсказка: Сначала отсортируйте интервалы по начальной точке, затем итерируйте и объединяйте.

Задача часто встречается на алгоритмических секциях в крупных IT-компаниях.

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Оптимальное решение O(n log n) время

func mergeIntervals(_ intervals: [[Int]]) -> [[Int]] {
    guard !intervals.isEmpty else { return [] }
    
    // Сортируем по начальной точке
    let sorted = intervals.sorted { $0[0] < $1[0] }
    
    var merged = [sorted[0]]
    
    for i in 1..<sorted.count {
        let current = sorted[i]
        let last = merged[merged.count - 1]
        
        // Если текущий интервал пересекается с последним объединённым
        if current[0] <= last[1] {
            // Объединяем: расширяем конец последнего интервала
            merged[merged.count - 1] = [last[0], max(last[1], current[1])]
        } else {
            // Нет пересечения, добавляем новый интервал
            merged.append(current)
        }
    }
    
    return merged
}

Пошаговое выполнение для примера 1:

Входные данные: [[1,3], [2,6], [8,10], [15,18]]

Шаг 1: Сортировка
Отсортировано: [[1,3], [2,6], [8,10], [15,18]]

Шаг 2: Инициализация
merged = [[1,3]]

Шаг 3: Итерация
  i=1: current=[2,6], last=[1,3]
       2 <= 3? ДА → Объединяем
       merged = [[1, max(3,6)]] = [[1,6]]
  
  i=2: current=[8,10], last=[1,6]
       8 <= 6? НЕТ → Добавляем
       merged = [[1,6], [8,10]]
  
  i=3: current=[15,18], last=[8,10]
       15 <= 10? НЕТ → Добавляем
       merged = [[1,6], [8,10], [15,18]]

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

Альтернативное решение со структурой Interval

struct Interval {
    let start: Int
    let end: Int
}

func mergeIntervals(_ intervals: [Interval]) -> [Interval] {
    guard !intervals.isEmpty else { return [] }
    
    let sorted = intervals.sorted { $0.start < $1.start }
    var merged = [sorted[0]]
    
    for interval in sorted.dropFirst() {
        let last = merged.removeLast()
        
        if interval.start <= last.end {
            merged.append(Interval(
                start: last.start,
                end: max(last.end, interval.end)
            ))
        } else {
            merged.append(last)
            merged.append(interval)
        }
    }
    
    return merged
}

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

let test1 = [[1,3], [2,6], [8,10], [15,18]]
print(mergeIntervals(test1))  // [[1,6], [8,10], [15,18]]

let test2 = [[1,4], [4,5]]
print(mergeIntervals(test2))  // [[1,5]]

// Дополнительные тесты
let test3: [[Int]] = []  // Пустой массив
print(mergeIntervals(test3))  // []

let test4 = [[1,5]]  // Один интервал
print(mergeIntervals(test4))  // [[1,5]]

let test5 = [[0,0]]  // Нулевая длина
print(mergeIntervals(test5))  // [[0,0]]

let test6 = [[1,2], [3,4], [5,6]]  // Без пересечений
print(mergeIntervals(test6))  // [[1,2], [3,4], [5,6]]

let test7 = [[1,5], [1,6], [1,7]]  // Все пересекаются в одной точке
print(mergeIntervals(test7))  // [[1,7]]

let test8 = [[2,3], [4,5], [6,7], [8,9], [1,10]]  // Один большой интервал
print(mergeIntervals(test8))  // [[1,10]]

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

Временная сложность:

  • Сортировка: O(n log n)
  • Итерация: O(n)
  • Общее: O(n log n)

Пространственная сложность: O(n)

  • Массив merged может содержать до n интервалов

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

  1. Пустой массив - вернуть пустой массив
  2. Один интервал - вернуть его как есть
  3. Все пересекаются - вернуть один большой интервал
  4. Никто не пересекается - вернуть отсортированный входной массив
  5. Одинаковые интервалы - вернуть один интервал

Почему именно эта логика?

Ключевое наблюдение: если интервалы отсортированы по началу, то для каждого интервала нам нужно проверить только с последним объединённым интервалом:

  • Если current[0] <= last[1] → пересекаются
  • Используем max(last[1], current[1]) чтобы найти конец объединённого интервала

Вариация с использованием свопа

func mergeIntervalsInPlace(_ intervals: inout [[Int]]) -> [[Int]] {
    guard !intervals.isEmpty else { return [] }
    
    intervals.sort { $0[0] < $1[0] }
    
    var writeIndex = 0
    
    for readIndex in 1..<intervals.count {
        if intervals[readIndex][0] <= intervals[writeIndex][1] {
            intervals[writeIndex][1] = max(
                intervals[writeIndex][1],
                intervals[readIndex][1]
            )
        } else {
            writeIndex += 1
            intervals[writeIndex] = intervals[readIndex]
        }
    }
    
    return Array(intervals[0...writeIndex])
}

Этот подход более оптимален по памяти для больших данных.

Рекомендация для интервью

Используйте первое решение:

  1. Оно ясно показывает логику
  2. Легко объяснить интервьюеру
  3. Правильно обрабатывает все граничные случаи
  4. O(n log n) достаточно оптимально
Merge Intervals | PrepBro