给定一个区间，在区间列表中查找所有区间
Given an interval, Find all intervals In a list of Intervals
假设我有一个这样的范围列表
[[1,3], [2,5], [4,6], [8,10], [12,15], [13,17]]
现在我想找到一个范围说 [3,11] 落入。我的算法应该给我这个范围落入的所有范围。例如这个输出应该是
Output - [1,3], [2,5], [4,6], [8,10]
我该如何解决这个问题？
PS：我知道线段树可能会有帮助。我可以在哪里构建树来存储间隔并查询位于间隔内的点，但是如何在给定间隔的情况下获取所有间隔。
区间树绝对是你需要的数据结构。我遇到了同样的问题，为了提高性能，我使用了 Augmented Interval Tree，其中每个节点除了范围的边界外，还包括与 相关的信息节点子树的最大值.
您可以在这里找到深入的解释和 Java 实现：Data Structures: Augmented Interval Tree to search for intervals overlapping
假设我有一个这样的范围列表
[[1,3], [2,5], [4,6], [8,10], [12,15], [13,17]]
现在我想找到一个范围说 [3,11] 落入。我的算法应该给我这个范围落入的所有范围。例如这个输出应该是
Output - [1,3], [2,5], [4,6], [8,10]
我该如何解决这个问题？
PS：我知道线段树可能会有帮助。我可以在哪里构建树来存储间隔并查询位于间隔内的点，但是如何在给定间隔的情况下获取所有间隔。
区间树绝对是你需要的数据结构。我遇到了同样的问题，为了提高性能，我使用了 Augmented Interval Tree，其中每个节点除了范围的边界外，还包括与 相关的信息节点子树的最大值.
您可以在这里找到深入的解释和 Java 实现：Data Structures: Augmented Interval Tree to search for intervals overlapping