algorithm - 用于 DVR 录制计划的数据模型

Question

DVR 需要存储要录制的节目列表。每个程序都有开始时间和持续时间。此数据需要以允许系统快速确定新记录请求是否与现有计划记录冲突的方式存储。

问题在于，仅仅查看是否有开始时间冲突的节目是不够的，因为较长节目的结尾可能会与较短节目重叠。我想可以创建一个数据结构来跟踪每个时间片的可用性，也许以半小时为粒度，但如果我们不能假设所有节目都在半小时边界开始和结束，并在分钟级别进行跟踪，那么这将失败在存储和查找方面似乎效率低下。

是否有一种数据结构允许按范围查询，您可以在其中提供下限和上限，并返回落在该范围内或与该范围重叠的所有元素的集合？

Answer 1

安interval tree (也许使用 augmented tree 数据结构？)正是您要找的。您可以将所有预定的记录输入到树中，当收到新请求时，检查它是否与任何现有间隔重叠。此查找和添加新请求都需要 O(log(n)) 时间，其中 n 是当前存储的间隔数。