用於快速時間間隔查找的數據結構

Question

我有一組時間間隔In =（an，bn）。我需要運行大量看看UPS在那裏我得到的時間噸和需要迅速返回包含噸，例如間隔，這些間隔，使得的< = T < = BN。

什麼是一個很好的數據結構或者算法？

如果重要，在我的情況下，和和bn是整數。

Answer 1

您要找的是一個Interval Tree（這是一種Range Tree）。

這些對象查找時間與其他樹結構（例如RB樹）相似，所以您應該看到使用類似Java TreeMap或STL映射的類似性能。

• Code for Red-black trees and interval trees從MIT
• 有一個在CGAL Library一個C++ implementation。
• 這裏有一個C# Implementation

Answer 2

這基本上是一個空間分割問題。你有一個很大的容器空間和一個特定的空間，它觸及什麼容器？很多遊戲必須解決這個問題，所以從這裏開始並不是一個壞主意。尋找關於「廣泛相位碰撞檢測」的文章。

要做到這一點最簡單的方法是你的電話號碼空間分成固定件數。每件作品都知道哪些作品集與作品相交，哪些是你在添加新作品集時計算出來的。現在，當你有一個點時，不是隻測試每一個集合，你只需要檢查該點中包含的集合。

另一個通用和高效的算法是二進制空間分區。該算法將您的空間分爲兩部分。每一方都會知道哪些組合與它相交。你可以遞歸地重複這個過程到你想要的精度（儘管創建一個小於最小集的範圍的細分是沒有意義的）。

Answer 3

你的問題只是一維的，所以它比在大多數遊戲中的空間分割問題簡單一些。 你可能只是一個簡單的BST，並且在每一片葉子中記住葉子左邊的區間列表。如果你有間隔A（0,10）和B（5,15），那麼樹的葉子將是（0與空列表），（5與A），（10與A，B）和（15與B）。

Answer 4

歡迎您來看看它究竟解決這一問題的C# implementation I've posted on CodePlex for IntervalTree。

伊多。