9

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

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

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

Range {
    Date start
    Date end
}

这是非规范化的，需要容器强制不重叠。对于两个相邻的范围，前一个结束将与下一个开始冗余。

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

B = 边界值，r = 范围

溴化溴

数据结构可能如下所示：

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

从本质上讲，它是一个具有交替类型的双向链表。

最终，我使用的任何数据结构都将在内存（应用程序代码）和关系数据库中表示。

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

4

8 回答 8

1

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

(RoomId, StartTime)

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

(boundary not between colBoudaryA and colBoundaryB)

加上额外的约束

(startBoundary < endBoundary)
于 2008-10-17T00:32:10.287 回答
1

双向链表效果很好，因为您只使用填充范围的内存，并且您只需要检查插入的重叠 - 在这一点上这样做几乎是微不足道的。如果有重叠，则新项目将被拒绝。

房间号
预订编号
上一个预订ID
下一个预订ID
开始时间日期
结束时间日期
优先
用户身份

优先级和用户 ID 允许日程安排具有优先级（教授可能比学生组更有影响力），以便新项目可以在插入过程中“敲掉”较低优先级的项目，用户 ID 允许电子邮件发送给颠簸的会议组织者。

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

-亚当

于 2008-10-17T00:33:46.320 回答
1

  1. 对于非重叠间隔，您可以使用起点对间隔进行排序。当您向此结构添加新间隔时，您只需检查起点和终点是否不属于此间隔集。要检查某个点 X 是否属于区间集，您可以使用二进制搜索来找到最近的起点并检查 X 是否属于它的区间。这种方法对于修改操作不是那么理想。

  2. 您可以查看间隔树结构 - 对于非重叠间隔，它具有最佳查询和修改操作。

于 2010-07-26T14:28:20.187 回答
1

如果你足够幸运（！）能够使用 Postgres，你可以使用一个tstzrange列，并应用一个约束来防止重叠。使用范围类型的好处是它会固有地防止开始大于结束。

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

您可能需要CREATE EXTENSION IF NOT EXISTS btree_gist，因为如果没有该扩展名，则不支持使用 && 创建要点。

于 2014-09-30T03:57:13.333 回答
0

很大程度上取决于您将如何处理数据，因此哪些操作需要高效。但是，我会考虑在 Start 和 End 的设置器中使用逻辑的 Ranges 的双向链接列表，以检查它现在是否与其邻居重叠，如果是，则缩小它们（或抛出异常，或者您想要处理尝试重叠）。

这提供了一个很好的简单链接列表，其中包含要阅读的预定时间段，但没有容器负责维护不重叠规则。

于 2008-10-17T00:34:03.683 回答
0

这在约束编程世界中称为“一元资源”约束。这方面有很多研究，特别是针对事件时间不固定的情况，您需要为每个事件找到时间段。有一个商业 C++ 包可以解决您的问题和更多Ilog CP，但这可能是矫枉过正。还有一个名为eclipse的开源版本（与 IDE 无关）。

于 2008-10-17T01:21:36.240 回答
0

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

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

我相信，其中一个相关的数据结构是R-Tree。这通常用于二维结构，但也适用于一维结构。

您还可以查找“艾伦的关系”以了解间隔 - 它们可能对您有所帮助。

于 2008-10-17T03:51:33.550 回答
0

我已经成功存储了开始时间和持续时间。重叠测试类似于

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
)

我认为没有测试，但希望你能理解

于 2009-04-19T13:35:17.940 回答