re:re:actable
Урок 053 минуты чтения

Как решать задачи на intervals?

На этой странице
Кратко

Задачи на intervals обычно решаются сортировкой по началу интервала и последующим проходом. Главные операции: merge intervals, detect overlap, insert interval, meeting rooms.

Вопрос

Как решать задачи на интервалы: слияние, пересечение, вставка?

Интервал

type Interval = [number, number]

Например:

[start, end]

Merge intervals

function mergeIntervals(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return []
 
  // Копируем: sort мутирует массив, а last[1] = ... менял бы сами интервалы из input.
  const sorted = intervals.map(([start, end]): Interval => [start, end]).sort((a, b) => a[0] - b[0])
 
  const result: Interval[] = [sorted[0]]
 
  for (let i = 1; i < sorted.length; i++) {
    const last = result[result.length - 1]
    const current = sorted[i]
 
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1])
    } else {
      result.push(current)
    }
  }
 
  return result
}

Пример: [[1, 3], [8, 10], [2, 6], [15, 18]]. После сортировки по началу:

         1  2  3  4  5  6  7  8  9  10 ... 15 16 17 18
[1, 3]   [-----]
[2, 6]      [-----------]
[8, 10]                       [------]
[15, 18]                                   [--------]
 
итог     [--------------]     [------]     [--------]
           [1, 6]              [8, 10]      [15, 18]
currentlast в resultПересекаются?result
---[1, 3]
[2, 6][1, 3]2 <= 3, да[1, 6]
[8, 10][1, 6]8 > 6, нет[1, 6], [8, 10]
[15, 18][8, 10]нет[1, 6], [8, 10], [15, 18]

Почему достаточно сравнивать только с последним? После сортировки по началу все следующие интервалы начинаются не раньше текущего. Если current не пересекается с последним, он не пересечется и ни с одним более ранним - они закончились еще раньше.

Math.max нужен для случая вложенных интервалов: [1, 10] и [2, 5] должны дать [1, 10], а не [1, 5].

Сложность:

Time: O(n log n)
Space: O(n)

Как узнавать interval-задачи?

  • meeting rooms;
  • calendar booking;
  • merge ranges;
  • overlapping intervals;
  • insert interval;
  • minimum arrows;
  • employee free time.

Что отвечать на собеседовании?

Для intervals я почти всегда сначала сортирую интервалы по start. После сортировки пересечения становятся локальными: достаточно сравнивать текущий интервал с последним в результате или соседним интервалом. Основная цена обычно O(n log n) из-за сортировки.

Что важно помнить: частые ошибки

  • Не отсортировать интервалы.
  • Путать inclusive/exclusive границы.
  • Не уточнить, пересекаются ли [1,2] и [2,3].
  • Мутировать input без предупреждения.
  • Неправильно обновлять end при merge.

Мини-шпаргалка

  • Sort by start.
  • Compare with previous/last.
  • Merge if overlap.
  • Complexity often O(n log n).
  • Уточняй границы.
  • Meeting rooms часто требует heap.

Документация

LeetCode: Merge Intervals.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам