查找包含给定数字的所有间隔

Question

我有一个可能重叠的间隔列表.然后,我有一个值,问题是找到包含该值的所有区间,值本身是包容性的.我见过几种方法,包括范围树,KD树等.但是,我想知道是否有针对此问题的特定优化解决方案,考虑到:

1. 间隔列表很长.(可能是50K或更多).
2. 间隔可能重叠.
3. 一旦我们开始查询,间隔列表就不会改变.
4. 列表一旦形成,就会以不同的值查询很多次.

有人可以建议一些方法来解决这个问题.提前致谢.

Answer 1

这是一个明确定义的问题,使用区间树(请参阅维基百科,此处和此处)可以最有效地解决问题.

我不建议使用哈希表,因为对于具有大量重叠的配置,您可能最终每个条目存储O(n)个段,需要O(n ^ 2)个存储总量.