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

Объединение перекрывающихся интервалов

2.3 Middle🔥 171 комментариев
#JavaScript Core

Условие

Напишите функцию mergeIntervals(intervals), которая принимает массив интервалов и объединяет все перекрывающиеся интервалы.

Требования

  1. Каждый интервал представлен массивом из двух чисел [start, end]
  2. Интервалы считаются перекрывающимися, если один начинается до окончания другого
  3. Результат должен содержать минимальное количество непересекающихся интервалов

Примеры

mergeIntervals([[1,3],[2,6],[8,10],[15,18]]);
// Результат: [[1,6],[8,10],[15,18]]

mergeIntervals([[1,4],[4,5]]);
// Результат: [[1,5]]

mergeIntervals([[1,4],[0,4]]);
// Результат: [[0,4]]

Сложность

Решите задачу с временной сложностью O(n log n).

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

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

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

Решение: Объединение перекрывающихся интервалов

Концепция и подход

Эта классическая задача часто встречается в интервьюшах и имеет элегантное решение. Ключевая идея — отсортировать интервалы по началу, затем пройти по ним один раз, объединяя те, которые перекрываются. Сложность O(n log n) достигается за счёт сортировки.

Базовая реализация

function mergeIntervals(intervals) {
  // Обработка пустого массива
  if (intervals.length === 0) return [];
  
  // Сортируем интервалы по началу
  // При одинаковом начале сортируем по концу
  intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  
  const merged = [intervals[0]];
  
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];
    
    // Если текущий интервал перекрывается с последним объединённым
    if (current[0] <= last[1]) {
      // Объединяем интервалы, расширяя конец если нужно
      last[1] = Math.max(last[1], current[1]);
    } else {
      // Интервалы не перекрываются, добавляем как новый
      merged.push(current);
    }
  }
  
  return merged;
}

Версия без изменения входного массива

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  
  // Создаём копию для сортировки
  const sorted = [...intervals].sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  
  const merged = [[...sorted[0]]];
  
  for (let i = 1; i < sorted.length; i++) {
    const [currentStart, currentEnd] = sorted[i];
    const lastMerged = merged[merged.length - 1];
    const [lastStart, lastEnd] = lastMerged;
    
    if (currentStart <= lastEnd) {
      // Объединяем
      lastMerged[1] = Math.max(lastEnd, currentEnd);
    } else {
      // Добавляем новый интервал
      merged.push([currentStart, currentEnd]);
    }
  }
  
  return merged;
}

TypeScript версия

type Interval = [number, number];

function mergeIntervals(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return [];
  
  // Сортируем по началу, затем по концу
  const sorted = intervals.sort(
    (a, b) => a[0] - b[0] || a[1] - b[1]
  );
  
  const merged: Interval[] = [sorted[0]];
  
  for (let i = 1; i < sorted.length; i++) {
    const [currentStart, currentEnd] = sorted[i];
    const [lastStart, lastEnd] = merged[merged.length - 1];
    
    if (currentStart <= lastEnd) {
      merged[merged.length - 1] = [lastStart, Math.max(lastEnd, currentEnd)];
    } else {
      merged.push([currentStart, currentEnd]);
    }
  }
  
  return merged;
}

Примеры использования

// Базовый пример
console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]

// Соприкасающиеся интервалы
console.log(mergeIntervals([[1,4],[4,5]]));
// [[1,5]]

// Полностью перекрывающиеся
console.log(mergeIntervals([[1,4],[0,4]]));
// [[0,4]]

// Один интервал содержит другой
console.log(mergeIntervals([[1,5],[2,3]]));
// [[1,5]]

// Множественные перекрытия
console.log(mergeIntervals([[1,2],[1,3],[1,4]]));
// [[1,4]]

// Уже отсортированные и объединённые
console.log(mergeIntervals([[1,2],[3,4],[5,6]]));
// [[1,2],[3,4],[5,6]]

// Пустой массив
console.log(mergeIntervals([]));
// []

// Один интервал
console.log(mergeIntervals([[1,5]]));
// [[1,5]]

Пошаговый разбор примера

Исходный массив: [[1,3],[2,6],[8,10],[15,18]]

  1. Сортировка: [[1,3],[2,6],[8,10],[15,18]] (уже отсортирован)
  2. Инициализация: merged = [[1,3]]
  3. Итерация 1: [2,6] начинается при 2 ≤ 3, объединяем → merged = [[1,6]]
  4. Итерация 2: [8,10] начинается при 8 > 6, добавляем → merged = [[1,6],[8,10]]
  5. Итерация 3: [15,18] начинается при 15 > 10, добавляем → merged = [[1,6],[8,10],[15,18]]

Вариант с использованием reduce

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  
  return sorted.reduce((merged, current) => {
    const last = merged[merged.length - 1];
    
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push(current);
    }
    
    return merged;
  }, [sorted[0]]);
}

Ключевые моменты

  • Сортировка: O(n log n) — самая дорогая операция
  • Основной цикл: O(n) — один проход по отсортированному массиву
  • Условие перекрытия: current[0] <= last[1] (строгое <=, а не <)
  • Расширение конца: Math.max() нужен для случаев, когда интервалы частично перекрываются
  • Неизменяемость: создаём копию при необходимости

Сложность

  • Временная: O(n log n) из-за сортировки
  • Пространственная: O(n) для результата и временного массива при сортировке
Объединение перекрывающихся интервалов | PrepBro