用于 DVR 录制计划的数据模型
DVR 需要存储要录制的节目列表。每个节目都有开始时间和持续时间。该数据需要以允许系统快速确定新的录制请求是否与现有预定录制冲突的方式存储。
问题在于，仅仅查看是否有节目的开始时间存在冲突是不够的，因为较长节目的结束可能与较短节目重叠。我想人们可以创建一个数据结构来跟踪每个时间片的可用性，也许以半小时为粒度，但如果我们不能假设所有节目都在半小时边界开始和结束，并在分钟级别进行跟踪，那么这就会失败在存储和查找方面似乎效率很低。
是否有一种数据结构允许按范围查询，在其中提供下限和上限，并返回属于该范围或重叠该范围的所有元素的集合？
A DVR needs to store a list of programs to record. Each program has a starting time and duration. This data needs to be stored in a way that allows the system to quickly determine if a new recording request conflicts with existing scheduled recordings.
The issue is that merely looking to see if there is a show with a conflicting start time is inadequate because the end of a longer program can overlap with a shorter one. I suppose one could create a data structure that tracked the availability of each time slice, perhaps at half-hour granularity, but this would fail if we cannot assume all shows start and end at the half-hour boundary, and tracking at the minute level seems inefficient, both in storage and look up.
Is there a data structure that allows one to query by range, where you supply the lower and upper bound and it returns a collection of all elements that fall within or overlap that range?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
一个间隔树（可能使用增强树数据结构？）正是您正在寻找的。您可以将所有计划的录制输入到树中，当收到新请求时，检查它是否与任何现有间隔重叠。此查找和添加新请求都需要 O(log(n)) 时间，其中 n 是当前存储的间隔数。
An interval tree (maybe using the augmented tree data structure?) does exactly what you're looking for. You'd enter all scheduled recordings into the tree and when a new request comes in, check whether it overlaps any of the existing intervals. Both this lookup and adding a new request take O(log(n)) time, where n is the number of intervals currently stored.