给定一个区间，找到所有的间隔在间隔

列表

[[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

回答