Модель данных для использования в расписании записи DVR

Question

Видеорегистратор должен хранить список программ для записи. Каждая программа имеет время начала и продолжительность. Эти данные должны храниться таким образом, чтобы система могла быстро определить, не конфликтует ли новый запрос на запись с существующими запланированными записями.

Проблема в том, что просто посмотреть, есть ли шоу с конфликтующим временем начала, неадекватно, потому что конец более длинной программы может совпадать с более короткой. Я предполагаю, что можно создать структуру данных, которая отслеживала бы доступность каждого временного среза, возможно, с полчасовой детализацией, но это не получилось бы, если бы мы не могли предположить, что все шоу начинаются и заканчиваются на получасовой границе, и отслеживание на минутном уровне кажется неэффективным, как в хранилище, так и в поиске.

Существует ли структура данных, позволяющая выполнять запросы по диапазону, когда вы задаете нижнюю и верхнюю границы, и она возвращает коллекцию всех элементов, которые попадают в этот диапазон или перекрывают его?

Answer 1

Дерево интервалов (возможно, с использованием структуры данных расширенное дерево ?) Делает именно то, что вы ищете. Вы вводите все запланированные записи в дерево, и когда приходит новый запрос, проверяете, перекрывает ли он какой-либо из существующих интервалов. И этот поиск, и добавление нового запроса занимают время O (log (n)), где n - количество сохраненных в настоящий момент интервалов.