Где применяется
1. Задача
У переговорной на день три брони: с 9:00 до 10:30, с 10:00 до 11:00 и с 14:00 до 15:00. Первые две пересекаются: вторая начинается в 10:00, а первая ещё идёт до 10:30. Значит, с 9:00 до 11:00 комната занята одним сплошным блоком. Календарю нужны именно такие блоки, чтобы показать свободное время между ними.
То же самое встречается в таблице маршрутизации файрвола (списке диапазонов адресов, по которому сетевой фильтр решает, что делать с пакетом). Допустим, там есть диапазоны 10-25 и 20-40. Адреса с 20 по 25 входят в оба. Если заменить их одним диапазоном 10-40, таблица станет короче и будет работать быстрее.
Задача в обоих случаях одна. Есть много диапазонов, и некоторые из них пересекаются или касаются. Нужно найти наименьшее число диапазонов, которые покрывают ровно те же точки.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитmergeIntervals([[8, 10], [1, 3], [15, 18], [2, 6], [9, 12], [5, 7]])Сливаем все интервалы, которые пересекаются или касаются. В исходном порядке пересекающиеся интервалы могут стоять далеко друг от друга.
Как узнать
Эти слова в условии значат этот паттерн
- слить перекрывающиеся интервалы
- вставить новый интервал в отсортированный список
- встречи, брони или диапазоны, которые пересекаются
- заданы как пары [начало, конец]
- свободное/занятое время между интервалами
Похоже, но не то
- Линия развёртки (подсчёт событий) (Sweep line (event counting))
Развёртка разбивает интервал на два события и считает их. Слияние держит интервалы целыми.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Убрать поменьше интервалов это жадный выбор по концу. Слияние просто соединяет пересечения.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Сортировка по началу это подготовка. Эта страница про проход, который идёт следом.
- Массив разностей (Difference array)
Он считает глубину перекрытия в каждой точке. Слияние возвращает интервалы, а не числа.
n до 1e6 стоит O(n log n), и всё это сортировка. Проход после неё стоит O(n).
На LeetCode
Задачи с диапазонами, которые пересекаются или касаются, где их нужно слить, вставить новый или пересечь два списка. Отсортируй по началу и пройди один раз, растягивая или закрывая текущий диапазон.
Это задача урока, касающиеся диапазоны тоже сливаются.
Список уже отсортирован, поэтому скопируй то, что кончается раньше нового диапазона, слей то, что с ним пересекается, и скопируй остаток.
Каждое число либо продлевает текущий диапазон на один, либо начинает новый.
Два отсортированных списка и два указателя, а два текущих диапазона пересекаются от большего начала до меньшего конца.