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

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

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

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

Range { 
    Date start 
    Date end 
}

这是非标准化的，并要求容器强制执行不重叠。对于两个相邻的范围，前一个'结束与下一个开始将是多余的。

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

B =边界值，R =范围

BrBrB

该数据结构可能看起来像：

Boundary { 
    Date value 
    Range prev 
    Range next 
} 

Range { 
    Boundary start 
    Boundary end 
}

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

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

我很好奇什么学术或行业尝试解决方案存在。

来源

2008-10-17 Steve Kuo

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

(RoomId, StartTime)

唯一约束在连续范围的情况下，你一定需要存放两件事情，一个边界，要么第二边界或长度。它通常被存储在第二边界，然后那种

(boundary not between colBoudaryA and colBoundaryB)

的两个边界上建立约束与附加约束

(startBoundary < endBoundary)

来源

2008-10-17 00:32:10 Sklivvz

双向链表效果很好，因为你只用做因为您已经填充了范围，所以您只需检查插入时的重叠情况 - 在这一点上这样做几乎是微不足道的。如果有重叠，新项目被拒绝。

 
RoomID 
ReservationID 
PreviousReservationID 
NextReservationID 
StartTimeDate 
EndTimeDate 
Priority 
UserID

优先级和用户ID允许时间表具有优先级（教授可能比一个学生组更大的影响力），这样的插入过程中一个新的项目可“击倒”低优先级的项目的出路，并用户ID允许将电子邮件发送给碰撞的会议组织者。

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

- 亚当

来源

2008-10-17 00:33:46

在很大程度上取决于你会用数据做什么，因此其操作需高效。不过，我会考虑在开始和结束的设置者中使用逻辑的双重链接的范围列表，以检查它是否与其邻居重叠，如果是，则缩小它们（或抛出异常，或者想要处理尝试交叠）。

这给出了一个很好的简单链接列表来读取预订期间，但没有负责维护无重叠规则的容器。

来源

2008-10-17 00:34:03 stevemegson

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

来源

2008-10-17 01:21:36

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

有关于该主题的整本书 - “时间数据库”处理的一部分。你可以看到两个是Darwen，Date和Lorentzos“Temporal Data and the Relational Model”和（在完全不同的极端）“Developing Time-Oriented Database Applications in SQL”Richard T. Snodgrass，Morgan Kaufmann Publishers，Inc.，旧金山，1999年7月，504 + xxiii页， ISBN 1-55860-436-7。这已经绝版，但在他的网站上以cs.arizona.edu提供PDF格式（因此谷歌搜索很容易找到）。

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

您也可以查找“Allen's Relations”间隔 - 它们可能对您有所帮助。

来源

2008-10-17 03:51:33

我已经成功存储开始时间和持续时间。对于重叠的测试会是这样的

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-19 13:35:17 dkretz

对于非重叠的间隔出发点你可以只排序您的时间间隔。当您为此结构添加新的时间间隔时，您可以检查开始点和结束点不属于此间隔集。要检查某个点X是否属于间隔集，可以使用二分查找来找到最近的起点并检查X属于它的间隔。这种方法对于修改操作来说并不是最佳的。
你可以看看Interval tree结构 - 对于非重叠的时间间隔它有最佳的查询和修改操作。

来源

2010-07-26 14:28:20 Dmitry

如果你是幸运的（！）足以使用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-30 03:57:13

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

回答

相关问题