給定一個區間，找到所有的間隔在間隔

列表

[[1,3], [2,5], [4,6], [8,10], [12,15], [13,17]]

範圍的列表現在我想找到一個範圍說[3,11]落在我的算法應該給我所有的範圍都在這個範圍內。例如，輸出這應該是

Output - [1,3], [2,5], [4,6], [8,10]

我如何去解決呢？ PS：我知道細分樹可能有幫助。在哪裏我可以構建樹來存儲間隔並查詢位於間隔內的點，但是如何獲得給定間隔的所有間隔。

2017-04-12 Muthu Rg

從https://en.wikipedia.org/wiki/Interval_tree我們有「具體來說，它允許人們有效地找到重疊的所有間隔與任何給定的時間間隔或點「 – mcdowella

如果這是給出一系列範圍的一次性任務，則只需對列表進行暴力破解。如果您需要經常查詢相同的數據，則可以構建一棵樹。如果數據經常變化但很少查詢，則可能會發現其他結構更有用。 –

Interval Tree絕對是您需要的數據結構。我面臨同樣的問題，爲了提高性能，我使用了擴展間隔樹，其中除了範圍的邊界外，每個節點還包含與節點的子樹的最大值有關的信息。

您可以在這裏找到一個深入的解釋和Java實現：Data Structures: Augmented Interval Tree to search for intervals overlapping

2017-04-12 16:08:07

回答