Не уверен насчет эффективности этих алгоритмов, но в голову почему-то приходят дерево отрезков и заметающая прямая.
Можно, например, разбить все время на отрезки по, скажем, пять минут. Тогда, к примеру, room[0] == 1 значит, что комната занята с 00:00 до 00:05. В этом случае запросами на сумму в дерево отрезков можно проверить доступность комнаты в заданный промежуток времени (сумма равна нулю), а добавлением значения ко всех элементам в отрезке можно "забронировать" комнату. Сложность обоих запросов O(log n), где n - размер массива room[].
e-maxx.ru/algo/segment_tree
codeforces.com/blog/entry/18051
Есть подход проще и при некоторых условиях даже эффективнее: одномерная заметающая прямая. Будем оперировать событиями вроде (13-30, open), (14-30, close). Пройдемся по отсортированным событиям, сохраняя число открытых на данный момент интервалов. Если между началом запроса и концом запроса счетчик был не равен нулю - интервал занят. Сложность (в случае массива с событями) - O(m logm) построение, O(m) запрос, O(m) добавление интервала, где m - число событий.
