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

Question

我需要一种数据结构，可以在单个维度内存储不重叠的范围。该维度的整个范围不必完全覆盖。

一个例子是会议室调度程序。该维度是时间。没有两个日程安排可以重叠。会议室并不总是被预定。换句话说，对于给定的时间，最多只能有一个日程安排。

一个快速解决方案是让范围存储开始和结束时间。

Range {
    Date start
    Date end
}

这是未经规范化的，需要容器强制执行不重叠。对于两个相邻的范围，前一个的结尾将与后一个的开始重复。

另一种方案可能涉及将每个范围存储一个边界值。但是对于连续的范围序列，边界值将始终比范围多一个。为了解决这个问题，序列可以表示为交替的边界值和范围：

B = 边界值，r = 范围

B-r-B-r-B

数据结构可能如下所示：

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

本质上，它是一种交替类型的双向链表。

无论我使用什么数据结构，它都将在内存（应用程序代码）和关系数据库中表示。

我很好奇有哪些学术或行业尝试过的解决方案存在。

- Steve Kuo

Answer 1

对于不重叠的间隔，您可以按起始点排序间隔。当您将新的间隔添加到此结构时，您只需检查起始点和终点是否不属于此间隔集。要检查某个点 X 是否属于区间集，您可以使用二分搜索找到最近的起始点，并检查 X 是否属于其区间。这种方法对于修改操作来说不是很优化。

您可以看一下Interval tree 结构- 对于非重叠区间，它具有最优查询和修改操作。

- Dmitry

Answer 2

双向链表很好用，因为你只使用填充范围所需的内存，并且只需要在插入时检查重叠 - 在那一点上几乎可以轻松地这样做。如果有重叠，新项目将被拒绝。

RoomID
ReservationID
PreviousReservationID
NextReservationID
StartTimeDate
EndTimeDate
Priority
UserID

优先级和用户ID允许安排具有优先级（教授可能比学生组更有影响力），以便在插入期间新项目可以“击败”较低优先级的项目，并且UserID允许向被撞会议组织者发送电子邮件。

您需要考虑添加一个指向每天第一次会议的表，以便可以优化搜索。

-Adam

- Adam Davis

Answer 3

规范化表示数据的方法是为每个时间单位存储一条记录。这可以在会议安排应用程序的示例中完成。您的约束将是唯一约束。

(RoomId, StartTime)

在连续范围的情况下，您必须存储两个东西，一个边界和第二个边界或长度。通常通过存储第二个边界，然后创建一种约束来完成两个边界的操作。

(boundary not between colBoudaryA and colBoundaryB)

同时还有额外的限制条件：

(startBoundary < endBoundary)

- Sklivvz

Answer 4

如果你足够幸运地使用Postgres，你可以使用一个tstzrange列，并应用一个约束来防止重叠。使用范围类型的好处是它本质上将防止开始时间大于结束时间。

ALTER TABLE "booking" 
ADD CONSTRAINT "overlapping_bookings" 
EXCLUDE USING gist ("period" WITH &&, "room" WITH =);

您可能需要执行CREATE EXTENSION IF NOT EXISTS btree_gist，因为在没有该扩展的情况下，使用&&创建Gist是不被支持的。

- Matthew Schinckel

Answer 5

很多事情取决于您将如何处理数据，因此需要哪些操作变得高效。然而，我会考虑使用带有范围的双向链表，并在Start和End的setter中添加逻辑来检查它是否与其邻居重叠，并在这种情况下缩小它们（或抛出异常，或以任何您想要处理尝试重叠的方式）。

这样可以得到一个漂亮简单的已预订时间段的链表，但没有容器负责维护不重叠规则。

- stevemegson

Answer 6

这被称为约束编程世界中的“一元资源”约束。在这个领域有很多研究，特别是当事件时间不固定时，需要为每个事件找到时间段。有一个商业C++软件包Ilog CP可以解决您的问题以及更多问题，但可能过于复杂。还有一个开源版本eclipse（与IDE无关）。

- David Nehme

Answer 7

这是非常复杂的，因为（在数据库世界中）您必须比较多行才能确定不重叠的范围。显然，当信息在内存中时，其他表示形式，如按时间排序的列表，是可能的。我认为，即使在列表中，您最好使用“开始+结束”符号。

关于这个主题有整本书——“时间数据库”处理的一部分。你可以看看 Darwen、Date 和 Lorentzos 的《时间数据和关系模型》，以及（在一个完全不同的极端）Richard T. Snodgrass 的《SQL 中开发面向时间的数据库应用程序》，Morgan Kaufmann Publishers, Inc.，旧金山，1999 年 7 月，504+xxiii 页，ISBN 1-55860-436-7。虽然已经绝版，但可以在他的网站 cs.arizona.edu 上作为 PDF 文件下载（因此通过谷歌搜索很容易找到）。

其中一个相关的数据结构是R-Tree，我相信。它通常用于二维结构，但也可以对一维结构有效。

你还可以寻找关于区间的 "Allen's Relations" - 它们可能对你有帮助。

- Jonathan Leffler

Answer 8

我已经成功地存储了开始时间和持续时间。检测重叠的测试可能是这样的：

WHERE NOT EXISTS (
   SELECT 1 FROM table
   WHERE BeginTime < NewBeginTime AND BeginTime + Duration > NewBeginTime
)
AND NOT EXISTS (
   SELECT 1 FROM table
   WHERE NewBeginTime < BeginTime AND NewBeginTime + NewDuration > BeginTime
)

我认为没有测试，但希望你能明白我的意思

- dkretz