假设我有一个这样的范围列表
[[1,3], [2,5], [4,6], [8,10], [12,15], [13,17]]
现在我想找到一个范围说[3,11]落入。我的算法应该给我这个范围落入的所有范围。例如，这个输出应该是
Output - [1,3], [2,5], [4,6], [8,10]
我该如何解决这个问题？
PS：我知道分段树可能会有所帮助。我可以在哪里构建树来存储区间并查询位于区间内的点，但是如何在给定区间的情况下获取所有区间。
问问题
2015 次
1 回答
1
区间树绝对是你需要的数据结构。我遇到了同样的问题，为了提高性能，我使用了增强间隔树，其中每个节点除了范围的边界外，还包括与节点子树的最大值相关的信息。
您可以在此处找到深入的解释和 Java 实现：数据结构：增强间隔树以搜索重叠的间隔
于 2017-04-12T16:08:07.767 回答