用于DVR录制时间表的数据模型 [英] Data model to use for a DVR's recording schedule

问题描述

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?

推荐答案

间隔树(也许使用增强树数据结构?)确实可以满足您的需求.您将所有预定的录音输入到树中，并在收到新请求时，检查它是否与任何现有间隔重叠.查找和添加新请求都需要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.

这篇关于用于DVR录制时间表的数据模型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！