Как проверить, хватит ли квартир для пересекающихся бронирований

За восемь ночей две квартиры дают шестнадцать квартиро-ночей. Если ровно столько уже забронировано, кажется, что мест достаточно. Но ночи разных дат не взаимозаменяемы: свободная квартира завтра не размещает гостя сегодня. Проверим не среднюю загрузку, а возможность закрепить каждый непрерывный заезд за конкретным объектом. Все даты и объекты далее условны.

Объявите интервал и запрет переезда

Есть шесть бронирований: A от 0 до 4, B от 1 до 3, C от 2 до 5, D от 3 до 6, E от 5 до 7, F от 6 до 8. Каждое относится к одной одинаковой квартире, которую гость занимает весь свой интервал. Разбить заезд между объектами, перенести даты или отказать гостю нельзя.

Запись [1,3) означает ночи, начинающиеся в 1 и 2. В момент 3 объект уже свободен: поэтому B и D могут стоять подряд. Уборка и передача ключей занимают нулевое время только по нашему условию. Для реальной проверки необходимый промежуток между заездами пришлось бы добавить до распределения.

Сумма проверяет только общий объём

Длительности A–F равны 4, 2, 3, 3, 2 и 2 ночам. Сумма 16 совпала с вместимостью двух объектов за восемь ночей: 2×8=16. Среднее необходимое число занятых квартир равно 16/8=2. Однако из этого не следует существование нужного расписания.

Между моментами 2 и 3 одновременно действуют A, B и C. Они требуют трёх разных объектов в одну и ту же ночь. Это нижняя граница: любая допустимая схема использует хотя бы три квартиры. Поменять названия объектов или переселить одного гостя позже не устраняет именно это одновременное требование.

Предъявите распределение, достигающее границы

Квартира 1 принимает A в [0,4), затем E в [5,7). Квартира 2 принимает B в [1,3), D в [3,6), F в [6,8). Квартира 3 принимает C в [2,5). Внутри каждой строки интервалы не пересекаются; каждый из шести заездов присутствует ровно один раз и не меняет квартиру.

Трёх достаточно, а двух недостаточно. Значит, минимум для полного набора точно равен трём. У этих трёх объектов суммарная вместимость 24 квартиро-ночи, использованы 16, свободны 8. Наличие свободных ночей не противоречит минимальности: они находятся в другие моменты.

Как восстановить проверяемую таблицу

Отсортируйте заезды по началу. Для очередного рассмотрите объекты, освободившиеся не позже его начала; если подходящего нет, добавьте строку. В нашем наборе A получает первую, B вторую, C третью. После выхода B в 3 ту же строку получает D; E и F заполняют указанные свободные интервалы.

Дополнительно пройдите все границы времени, удаляя закончившиеся заезды перед добавлением новых. Число занятых квартир в восьми единичных ночах равно 1,2,3,3,2,2,2,1. Максимум три согласуется с построенной схемой, а сумма этих чисел снова равна 16. Так проверяются и объём, и размещение.

Что этот минимум не устанавливает

Это не выбор выгодного числа покупаемых квартир и не прогноз реального спроса. Цена, уборка, разные требования гостей и доступность конкретных объектов исключены. При таких ограничениях одна проверка пересечений может стать недостаточной. Сохраните сами интервалы и условия совместимости: равенство суммарных ночей остаётся лишь одной необходимой проверкой, а полное распределение показывает выполнимость заданного набора.

Ограничения разбора

• Все интервалы, объекты и длительности вымышлены; не описываются действующие правила аренды или сервиса бронирования.
• Интервалы полуоткрыты; конец обрабатывается до начала в ту же точку. Нулевое время подготовки, одинаковые доступные объекты и отсутствие переездов — строгие условия.
• Каждый из шести заездов обязан быть размещён целиком. Отбор выгодной части бронирований, цена, покупка дополнительных объектов и реальный спрос не исследуются.
• Минимум три доказан для полного заданного набора. Дополнительные ограничения доступности/совместимости требуют новой проверки, не автоматически того же ответа.

Источники