Как определить вхождение в промежуток времени?

Question

[wangler]

Здравствуйте.
Прошу помощи сложить алгоритм для решения такой задачки по расчету времени:
В табличке есть две timestamp строки (начало интервала и конец). Например от 13-30 до 14-30.
Таких записей несколько, на одном промежутке времени. Как можно определить, какие промежутки уже "заняты"? Возможно уже есть решение в виде готовой библиотеки для работы с такими значениями, в любом случае буду рада любому совету.

Comments

[Roman_Kh]

Задачу сначала четко опишите: структуру и формат данных, примеры табличек с записями, точно сформулируйте что значит "промежуток занят", структуру и формат результата работы алгоритма

Answer 1

[delfphe]

Не уверен насчет эффективности этих алгоритмов, но в голову почему-то приходят дерево отрезков и заметающая прямая.

Можно, например, разбить все время на отрезки по, скажем, пять минут. Тогда, к примеру, 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 - число событий.

Answer 2

[Владимир Олохтонов]

Надо найти полное покрытие заданных интервалов с помощью минимального количества объединенных интервалов.

Я правильно понял вашу задачу? Подобный алгоритм рассматривался в курсе по алгоритмам на stepic.org, с телефона не получилось найти его название.