Как решать задачи на 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]| current | last в 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.