Паттерн: Интервалы

Признак в условии

• массив пар [начало, конец]
• «слить пересекающиеся», «можно ли посетить все», «сколько нужно комнат»
• расписания, бронирования, отрезки времени

Идея

Почти всё решается сортировкой по началу и одним проходом. Задачи про «сколько одновременно» - сканирующей прямой: отдельно отсортированные начала и концы, идём по времени и считаем открытые интервалы.

Шаблон

const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const out = [sorted[0].slice()];
for (let i = 1; i < sorted.length; i++) {
  const last = out[out.length - 1];
  if (sorted[i][0] <= last[1]) last[1] = Math.max(last[1], sorted[i][1]);
  else out.push(sorted[i].slice());
}

Сложность

Время O(n log n) на сортировку, память O(n).

Частые ошибки

• last[1] = cur[1] вместо Math.max: вложенный интервал обрезает предыдущий
• мутация входных интервалов
• путаница строгого и нестрогого сравнения на касании границ - надо уточнить у интервьюера

Мнемоника

«Отсортируй по началу, тяни конец максимумом»

Не путать с

• Жадность - интервалы почти всегда решаются жадно после сортировки: сортировка по началу - слияние, по концу - максимум непересекающихся
• Скользящее окно - окно - про непрерывный участок одного массива; интервалы - про множество отрезков с началом и концом

Задачи на этот паттерн

• слияние интервалов
• можно ли посетить все встречи
• вставка интервала
• сколько нужно переговорок
• минимум удалений интервалов
• пересечение двух списков

Суть

Интервальные задачи почти всегда начинаются с сортировки. После неё каждый интервал нужно сравнить только с соседом или последним выбранным, и O(n²) превращается в O(n log n).

Как распознать по условию

• «встречи», «бронирования», «отрезки», «расписание»;
• слить, вставить, найти пересечения;
• «сколько комнат / ресурсов одновременно»;
• «максимум непересекающихся», «минимум удалений».

Пересечение двух интервалов

Закрытые [a1, a2] и [b1, b2] пересекаются, если a1 <= b2 && b1 <= a2. Уточняй у интервьюера, включается ли конец: для встреч [9, 10) и [10, 11) пересечения нет.

Слияние

function merge(intervals) {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0].slice()];
  for (let i = 1; i < intervals.length; i++) {
    const [s, e] = intervals[i];
    const last = res.at(-1);
    if (s <= last[1]) last[1] = Math.max(last[1], e); // max!
    else res.push([s, e]);
  }
  return res;
}

Число переговорок (события)

function rooms(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 j = 0, used = 0, best = 0;
  for (let i = 0; i < starts.length; i++) {
    while (j < ends.length && ends[j] <= starts[i]) { j++; used--; }
    used++;
    best = Math.max(best, used);
  }
  return best;
}

Жадный выбор: сортировка по концу

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

Сложность

Сортировка O(n log n) доминирует. Если вход уже отсортирован (вставка интервала), хватит O(n).

Ловушки

• last[1] = e вместо Math.max: вложенный интервал укоротит слитый.
• sort() без компаратора сравнивает строки: [10, 12] окажется раньше [9, 11], потому что "10,12" < "9,11".
• Мутация входного массива: скажи об этом или скопируй.
• Пустой вход.

Что спросят на собесе

• Слей пересекающиеся интервалы.
• Сколько нужно переговорок?
• По началу или по концу сортировать и почему?
• Вставь интервал в отсортированный список за O(n).