Задачи на интервалы: слияние, пересечение и планирование встреч

Почему это отдельная тема

Задачи на интервалы выглядят разрозненно: где-то нужно слить отрезки, где-то посчитать переговорки, где-то найти пересечение расписаний. Но за всеми ними стоит один и тот же приём — отсортировать и пройти один раз.

Если этот приём в голове, семейство задач закрывается почти автоматически. Если нет — каждая кажется новой, и на собеседовании легко потеряться.

Практическая ценность тоже реальная: календари, бронирование, тарификация по времени, объединение диапазонов IP-адресов — везде те же алгоритмы.

Базовая задача: слияние интервалов

Дан список отрезков, нужно слить все пересекающиеся.

[[1,3], [2,6], [8,10], [15,18]]
 →  [[1,6], [8,10], [15,18]]

Ключевая идея: отсортировать по левой границе. После сортировки все интервалы, которые могут пересечься с текущим, идут подряд — а значит, достаточно одного прохода.

function merge(intervals) {
  if (intervals.length === 0) return [];

  // сортируем по началу отрезка
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const result = [sorted[0]];

  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    const last = result[result.length - 1];

    if (start <= last[1]) {
      // пересекаются — расширяем правую границу
      last[1] = Math.max(last[1], end);
    } else {
      // разрыв — начинаем новый интервал
      result.push([start, end]);
    }
  }

  return result;
}

merge([[1, 3], [2, 6], [8, 10], [15, 18]]);
// [[1, 6], [8, 10], [15, 18]]

Два момента, которые стоит проговорить на собеседовании.

Почему Math.max, а не просто end. Один интервал может целиком содержаться в другом: [1,10] и [2,3]. Без максимума правая граница схлопнется с 10 до 3. Это самый популярный баг в этой задаче.

Почему <=, а не <. Отрезки [1,3] и [3,5] касаются в точке. Считать ли их пересекающимися — вопрос условия. Обычно да, но уточнить вслух стоит: это ровно тот краевой случай, который интервьюер закладывал.

Сложность — O(n log n) на сортировку плюс O(n) на проход. Сортировка доминирует.

Вставка интервала в отсортированный список

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

Можно добавить в конец и запустить предыдущий алгоритм — но это O(n log n), а здесь достаточно O(n). Разбиваем на три фазы.

function insert(intervals, newInterval) {
  const result = [];
  let [start, end] = newInterval;
  let i = 0;

  // 1. всё, что целиком левее нового — копируем как есть
  while (i < intervals.length && intervals[i][1] < start) {
    result.push(intervals[i]);
    i++;
  }

  // 2. всё, что пересекается — поглощаем в новый интервал
  while (i < intervals.length && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  result.push([start, end]);

  // 3. остаток копируем
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

insert([[1, 3], [6, 9]], [2, 5]);
// [[1, 5], [6, 9]]

Три последовательных цикла вместо одного с ветвлениями читаются заметно лучше. Здесь это не стилистика: каждая фаза имеет понятный смысл, и логику проще проверить.

Пересечение двух расписаний

Даны два отсортированных списка занятых интервалов, нужно найти общие промежутки. Классическая формулировка — «когда оба человека свободны».

Здесь работают два указателя:

function intervalIntersection(first, second) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < first.length && j < second.length) {
    // пересечение двух отрезков, если оно есть
    const start = Math.max(first[i][0], second[j][0]);
    const end = Math.min(first[i][1], second[j][1]);

    if (start <= end) {
      result.push([start, end]);
    }

    // двигаем тот указатель, чей отрезок кончается раньше
    if (first[i][1] < second[j][1]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}

intervalIntersection(
  [[0, 2], [5, 10], [13, 23]],
  [[1, 5], [8, 12], [15, 24]]
);
// [[1, 2], [5, 5], [8, 10], [15, 23]]

Формула пересечения — [max(начал), min(концов)], и если начало больше конца, пересечения нет. Правило «двигаем указатель того интервала, который кончается раньше» гарантирует, что мы ничего не пропустим: закончившийся отрезок больше ни с чем пересечься не может.

Сложность — O(n + m), сортировка не нужна, списки уже упорядочены.

Переговорки: сколько комнат нужно

Дан список встреч, нужно определить минимальное количество переговорок, чтобы ни одна не пересеклась.

[[0,30], [5,10], [15,20]]  →  2

Задача выглядит иначе, но решается тем же приёмом — если посмотреть на неё правильно. Нас не интересуют конкретные встречи, только события: в момент начала комната занимается, в момент конца освобождается.

function minMeetingRooms(intervals) {
  const starts = intervals.map((i) => i[0]).sort((a, b) => a - b);
  const ends = intervals.map((i) => i[1]).sort((a, b) => a - b);

  let rooms = 0;
  let maxRooms = 0;
  let endIndex = 0;

  for (const start of starts) {
    // все встречи, закончившиеся до начала текущей, освобождают комнаты
    while (endIndex < ends.length && ends[endIndex] <= start) {
      rooms--;
      endIndex++;
    }

    rooms++;
    maxRooms = Math.max(maxRooms, rooms);
  }

  return maxRooms;
}

minMeetingRooms([[0, 30], [5, 10], [15, 20]]); // 2

Приём с раздельной сортировкой начал и концов называется свипом (sweep line) и встречается во множестве задач: максимальное число одновременных подключений, пиковая нагрузка, наибольшее перекрытие диапазонов.

Альтернатива — куча минимумов, где хранятся времена окончания текущих встреч. Обе версии O(n log n), выбирайте ту, что понятнее объяснить.

Максимум непересекающихся встреч

Обратная задача: встреч много, комната одна, нужно провести как можно больше.

Здесь работает жадный алгоритм, но с важным нюансом — сортировать надо по концу, а не по началу.

function maxNonOverlapping(intervals) {
  if (intervals.length === 0) return 0;

  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let count = 1;
  let lastEnd = sorted[0][1];

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= lastEnd) {
      count++;
      lastEnd = sorted[i][1];
    }
  }

  return count;
}

Интуиция: выбирая встречу, которая заканчивается раньше всех, мы оставляем максимум места для остальных. Сортировка по началу здесь даёт неверный ответ — длинная встреча, начавшаяся первой, заблокирует несколько коротких.

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

Шпаргалка

Типичные ошибки

Забытый Math.max при слиянии — вложенные интервалы схлопывают правую границу.

Сортировка по началу в жадной задаче — даёт неоптимальный ответ, и на маленьких тестах это не видно.

Изменение входного массива. sort в JavaScript сортирует на месте. Если функция не должна портить аргумент, копируйте через spread — как во всех примерах выше.

Сравнение строк вместо чисел. [[10, 20], [9, 15]].sort() без компаратора отсортирует лексикографически, и 10 окажется раньше 9. Компаратор обязателен всегда.

Необработанный пустой вход. intervals[0] на пустом массиве даёт undefined и падение на следующей строке.

Что запомнить

• Почти все задачи на интервалы начинаются с сортировки.
• Для слияния сортируем по началу, для жадного выбора — по концу.
• Пересечение двух отрезков — это [max(начал), min(концов)], и оно существует, только если начало не больше конца.
• Свип по отдельно отсортированным началам и концам решает задачи про одновременность.
• Уточняйте у интервьюера, считаются ли касающиеся отрезки пересекающимися.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→