Ответ 1
Если у вас есть набор резервирований и фиксированное количество комнат, то вопрос заключается не в том, как максимизировать использование, а в том, чтобы проверить, действительно ли оговорки могут быть реализованы вообще или нет. Использование, очевидно, остается тем же, если все оговорки реализованы.
Еще один возможный случай использования заключается в том, что у вас есть набор зарезервированных номеров, которые, как вы знаете, могут быть реализованы, и затем вы пытаетесь установить новое резервирование, то есть новый клиент хочет сделать новое бронирование, и вы хотите проверить, может переместить некоторые из оговорок, чтобы создать место для нового.
В обоих случаях фактический вопрос заключается в том, как проверить, может ли реализоваться данный набор оговорок.
Для нереляционных оговорок это тривиально, поэтому предположим, что они могут быть реализованы, и вы хотите проверить, могут ли быть реализованы также перемещаемые оговорки.
Первая проверка - рассчитать на каждую ночь количество оговорок за ту ночь; если в любое время суток количество резервирований превышает количество доступных номеров после того, как фиксированные оговорки будут учтены, вы не сможете реализовать оговорки любыми трюками; ваш отель забронирован на ту ночь.
В противном случае вы можете использовать жадный алгоритм для попытки решения: обработать оговорки в порядке их дат начала и забронировать каждую резервацию в первую комнату (например, в порядке номеров), которая доступна. Если это дает вам решение, то вы поняли оговорки, и все готово.
Если это не сработает, вы можете использовать GRAPH COLORING для решения проблемы, и это универсальное решение. Постройте граф, где каждое резервирование является node, а два узла (резервирование) связаны тогда и только тогда, когда они перекрываются по времени. Включите фиксированные (не перемещаемые) оговорки на графике. Затем сделайте полную окраску графика с N цветами (N = общее количество комнат в вашем отеле), как только вы определили фиксированные оговорки с номерами номеров, к которым они относятся.
Вы можете обрабатывать также только частично гибкие резервирования таким образом, добавляя ссылку от резервирования r к специальному n-preolored node для комнаты n тогда и только тогда, когда резервирование НЕ может быть реализовано в комнате n (например, нижняя комната класс).
Этот же алгоритм раскраски графа успешно используется, например, в компиляторах для распределения регистров.
Конечно, вопрос заключается в том, как эффективно выполнять гравюру; для этого есть готовые реализации.
Удачи!