c++ - 查找所有重叠一点的时间间隔

Question

考虑一维的大量浮点间隔，
例如

 [1.0, 2.5],                1.0 |---------------|2.5

 [1.5, 3.6],                      1.5|---------------------|3.6

 .....

期望找到包含给定点的所有间隔。例如，给定点= 1.2，则算法应返回第一个间隔，如果给定点= 2.0，则应返回上例中的前两个间隔。

在我要解决的问题中，此操作需要以大量间隔重复多次。因此，不需要强力搜索，并且性能是重要的因素。

搜索之后，我看到在计算几何的上下文中使用间隔跳过列表解决了此问题。我想知道是否有任何简单，有效的C++实现。

编辑:要更精确地解决该问题，有N个间隔，对于M个点，应确定哪个间隔包含每个点。 N和M是大数，其中M大于N。

Answer 1

建议使用CGAL range trees:

维基百科说interval trees(一维范围树)可以“有效地找到与任何给定间隔或点重叠的所有间隔”。