查找包含给定数字的所有间隔 [英] Find all intervals containing a given number

问题描述

我有一个可能重叠的间隔列表。而且，我有一个值，问题是找到包含该值的所有间隔，值本身是包含值。
我已经看到了几种方法，包括范围树，KD树等。但是，我想知道是否有针对此问题的特定优化解决方案，考虑：

1. 间隔列表很长。 （可能在50K以上）


2. 间隔可能重叠。


3. 一旦我们开始查询，间隔列表不会改变。 li>
   
4. 一旦形成的列表被查询了很多次，具有不同的值。

可以有人建议一些解决办法。感谢提前。

解决方案

这是一个定义明确的问题，使用间​​隔树最有效地解决了（参见维基百科，这里和 here ）作为解释。

我不会推荐哈希表，因为对于有很多重叠的配置，您最终可能会存储O（n）段每个条目，需要O（n ^ 2）存储总计。

I have a list of intervals which might be overlapping. And, then I have a value and the problem is to find all the intervals which contain that value, the value itself being inclusive. I have seen several approaches including range trees, KD trees etc. But, I am wondering if there is a specific optimized solution for this problem, considering:

1. The list of intervals is long. (Might be 50K or more).
2. The intervals may be overlapping.
3. The list of interval does not change once we start querying.
4. The list once formed, is queried for a large number of times with different values.

Could someone suggest some approaches to solve this. Thanks in advance.

解决方案

This is a well-defined problem that is most efficiently solved using an interval tree (see wikipedia, here and here) for an explanation.

I wouldn't recommend a hash table since for configurations with a lot of overlap you may end up storing O(n) segments per entry, requiring O(n^2) storage total.

这篇关于查找包含给定数字的所有间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！