Где применяется
1. Задача
У офиса есть общие переговорные комнаты. Встречи на день: [[0,30],[5,10],[15,20]], время в минутах. Сколько комнат нужно, чтобы каждой встрече хватило места?
Слияние из прошлого урока здесь не поможет. Возьми встречи [0,30] и [5,10]. Слияние превратит их в один блок [0,30]. Но с 5-й по 10-ю минуту идут обе встречи, и комнат для них нужно две. После слияния этого количества уже не видно.
Поэтому вопрос ставится так: сколько встреч идёт одновременно в самый загруженный момент дня. Это число, пик, и есть количество нужных комнат. Тот же вопрос встречается в другом виде: «сколько соединений с базой данных было открыто одновременно» или «сколько пользователей было онлайн в одну и ту же секунду».
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитmaxOverlap([[1, 4], [2, 5], [7, 9], [3, 6], [5, 8]])| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| [1,4] | ■ | ■ | ■ | ■ | |||||
| [2,5] | ■ | ■ | ■ | ■ | |||||
| [7,9] | ■ | ■ | ■ | ||||||
| [3,6] | ■ | ■ | ■ | ■ | |||||
| [5,8] | ■ | ■ | ■ | ■ |
Сколько интервалов открыто в самый загруженный момент? Каждый интервал это строка на шкале.
Как узнать
Эти слова в условии значат этот паттерн
- максимум одновременно пересекающихся встреч/интервалов
- минимум комнат/ресурсов
- самый загруженный момент времени
- сколько интервалов покрывают заданную точку
- события, происходящие в одно и то же время
Похоже, но не то
- Интервалы: слияние и вставка (Intervals: merge & insert)
Слияние держит интервалы целыми и соединяет соприкасающиеся. Развёртка про них забывает и считает.
- Массив разностей (Difference array)
Это развёртка, в которой координаты и есть индексы массива. Ей нужен узкий плотный диапазон.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Куча держит открытые интервалы и знает, какой кончится раньше. Счётчик знает только сколько их.
- Префиксные суммы (Prefix sums)
Префиксные суммы отвечают по фиксированным позициям массива. Развёртка идёт по событиям в порядке сортировки.
n интервалов дают 2n событий, значит O(n log n) на сортировку. Сам проход стоит O(n).
На LeetCode
Задачи, где спрашивают, сколько диапазонов открыто в самый загруженный момент или в заданный момент. Преврати каждый диапазон в плюс 1 в начале и минус 1 в конце, отсортируй события и пройди по ним со счётчиком.
Рождение прибавляет один, год смерти убирает один, а ответом будет самый ранний год с наибольшим счётом.
Это переговорные из урока, только диапазоны с общей точкой здесь пересекаются, поэтому начало открывается раньше равного ему конца.
После каждой брони заново пройди по всем событиям начала и конца и верни пик.
Когда начала и концы отсортированы, цветущих в день столько, сколько начал до него минус концов раньше него, и оба числа находит бинарный поиск.