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