单个维度内非重叠范围的数据结构

Question

我需要一个可以在一个维度内存储非重叠范围的数据结构.不需要完全覆盖整个尺寸范围.

一个例子是会议室调度程序.维度是时间.没有两个时间表可能重叠.会议室并非始终安排.换句话说,对于给定时间,最多可以有一个时间表.

快速解决方案是存储开始和结束时间的范围.

Range {
    Date start
    Date end
}

这是非规范化的,要求容器不强制执行.对于两个相邻的范围,前一个'结束将在下一个开始时是多余的.

另一种方案可能涉及存储每个范围的一个边界值.但是对于连续的范围序列,总会有一个边界值而不是范围.为了解决这个问题,序列可以表示为交替的边界值和范围:

B =边界值,r =范围

BrBrB

数据结构可能如下所示:

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

从本质上讲,它是具有交替类型的双向链表.

最终,我使用的任何数据结构都将在内存(应用程序代码)和关系数据库中表示.

我很好奇学术界或行业所尝试的解决方案是什么.

Answer 1

表示数据的标准化方法是存储每个时间单位的记录。这可以在会议安排应用程序的示例中完成。你的约束将是一个独特的约束

(RoomId, StartTime)

在连续范围的情况下，您必须存储 2 个内容，一个边界和第二个边界或长度。通常是通过存储第二个边界然后在该类型的两个边界上创建约束来完成的

(boundary not between colBoudaryA and colBoundaryB)

附加约束条件是

(startBoundary < endBoundary)