單維內非重疊範圍的數據結構

我需要一個數據結構，可以在單維內存儲非重疊範圍。維度的整個範圍不需要完全覆蓋。單維內非重疊範圍的數據結構

一個例子是會議室調度程序。維度是時間。沒有兩個時間表可能會重疊。會議室並不總是安排。換句話說，在給定的時間內最多隻能有一個時間表。

快速解決方案是存儲開始和結束時間的範圍。

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

單維內非重疊範圍的數據結構

回答

相關問題