SeniorДизайнРедкоЕщё не отвечали
Даны даты заезда и отъезда каждого гостя (заезд строго раньше отъезда, поэтому каждый гость проводит хотя бы одну ночь). Спроектируйте алгоритм, находящий максимальное число гостей, одновременно проживающих в гостинице. В общий день уезжающий гость выезжает раньше, чем заезжает новый. Опишите структуры данных, сложность по времени и как вы разрешаете ничью, когда интервалы соприкасаются в одной точке.
Используйте sweep line: разбейте каждое проживание на событие заезда +1 и отъезда −1, отсортируйте по времени и пройдите, ведя текущий счётчик, чей максимум и есть ответ. В общий момент обрабатывайте отъезды раньше заездов. O(N log N) на сортировку.
- ✗Ошибиться в разрешении ничьей в общий день, считая отъезд и заезд одновременными
- ✗Использовать массив по дням, который раздувается при огромном диапазоне дат
- ✗Забыть, что отъезд освобождает место, поэтому
−1применяется в нужный момент
- →Как ещё и сообщить, в какой день (или дни) был пик загрузки?
- →Что меняется, если нужно поддержать поток проживаний, добавляемых по одному?
Оглавление
Сценарий
Гостиница хочет знать максимальную одновременную загрузку по датам заезда/отъезда гостей.
Разбор
Это классическая sweep line (как «meeting rooms II»):
- Каждое проживание
[in, out)даёт два события:(in, +1)и(out, −1). - Сортируем события по времени; при совпадении сначала идут
−1(уезжает раньше, чем заезжает). - Проходим слева направо, ведём текущий счётчик
curи его максимумpeak.
Сложность: O(N log N) на сортировку, O(N) на проход, O(N) памяти.
Оглавление
