区间交集是一个简单但并非易解的问题。
已有两次回答：
第一种解决方案的时间复杂度为O(n)，第二个解决方案针对数据库（其时间复杂度当然小于O(n)）。
我遇到了相同的问题，但我的n很大，并且我不在数据库中。
这个问题似乎与将2D点存储以便快速检索位于矩形内的点非常相似，但我不知道如何映射这个问题。
那么，你会用什么数据结构来存储这组区间，以便搜索区间的成本低于O(n)?（使用Java可用的库获取额外积分）
编辑：
我想要得到所有相交区间的子集，也就是说，搜索范围可能与多个区间相交。
所需在Java中进行时间复杂度低于O(n)的方法是：
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
Range是一个包含int start和end的一对的类。
这不是一个不可能的问题，我已经有了解决方案，我只是想看看是否有更标准/更简单的方法来做到这一点。
标准做法是使用区间树。
在计算机科学中，区间树是一种用于存储区间的树形数据结构。它可以高效地查找与任何给定的区间或点重叠的所有区间。通常用于窗口查询，例如，在计算机化地图内查找所有在矩形视口内的道路，或者在三维场景内查找所有可见元素。类似的数据结构是线段树。
常见的解决方案是访问每个区间并测试它是否与给定的点或区间相交，这需要O(n)的时间，其中n是集合中区间的数量。由于查询可能返回所有区间，例如如果查询是一个大的区间与集合中所有区间相交，那么这是渐进最优的；但是，我们可以通过考虑输出敏感算法来进行更好的处理，其中运行时间以m表示，即查询产生的区间数。区间树的查询时间为O(log n + m)，初始创建时间为O(n log n)，同时将内存消耗限制为O(n)。创建后，区间树可以是动态的，允许在O(log n)中高效地插入和删除区间。如果区间的端点在小整数范围内（例如在范围[1，...，O(n)]中），则存在更快的数据结构[1]，其预处理时间为O(n)，查询时间为O(1+m)，用于报告包含给定查询点的m个区间。
编辑： 听起来这个解决方案或多或少类似于区间树。 更完整的区间树实现可以在这里找到。
class TreeNode
{
public:
long pivot;
List<Range> leaves; //Any ranges that intersect the pivot
TreeNode left; //Tree nodes that fall to the left of the pivot
TreeNode right; //Tree nodes that fall to the right of the pivot
};
预处理 O(n log n):
搜索:
向下遍历树形结构，直到中心点>测试区间的起始位置。
2a. 将叶子节点添加到结果中。
示例:
区间:
树形结构:
4
--------------+------------------
3 | 7
| 1-4 |
| 2-4 |
| 0-5 |
| 4-5 |
---------+------ --------+--------
2 | null 6 | null
-----+---- 2-3 ----+---- 3-7
null | null null | null
0-2 2-6
1-2
非重叠范围：
O(n log n) 准备工作：
搜索：
从二分搜索开始的迭代器，直到找到一个 Start > TestRange.End：
2a. 如果当前范围在 TestRange 内，则将其添加到结果中。
交叉范围：
预处理 O(n log n)：
Make a second vector of ints. This represents the point at which you can stop searching.
int stop[size];
stop[size-1] = Ranges[size - 1].start;
for (int i = size - 2; i >= 0; i--)
{
stop[i] = min(Ranges[i].start, stop[i+1]);
}
搜索:
从二分查找开始的迭代器，直到stop[i] > TestRange.End：
2a. 如果当前范围在TestRange内，则将其添加到结果中。
如果范围重叠，并且想要检索与给定目标范围相交（或包含）的所有范围，则上述大多数解决方案似乎不起作用。
正如一些人指出的那样，如果（最坏情况下）所有范围恰好与目标范围相交（例如，如果目标范围为{0..MAXINT}或类似范围），则当然需要O(n)来返回n个范围。
但是有趣的典型/平均情况是否只有很小的n个范围与目标范围相交？称与之相交的数量为“m”--在这种情况下，你可能能够做得像O(m)一样好。如果n = 10^9，m = 10，那么这将是一个决定胜负的差异。
考虑一个简单的文本文档案例，其中有各种标记了其“类型”的区域。也许您想要查找所有包含或与给定连续文本范围（例如段落）相交的标记单元。在 HTML、XML 或类似格式中，这些标记只能是包含目标范围至少包含一些字符的文本节点的祖先。在每个节点都有父指针的典型表示中，复杂度为 O(m) ——比 O(n) 好得多，特别是因为 m 对于短或同步目标范围仅为树嵌套深度，而大型 XML 文档实际上变得更加丰富而不是更深。我认为这就是原问题的意思，但恐怕我没有看到解决这个问题的答案。如果这不是原问题的关键点，那么我想把它作为一个新问题提出。
这取决于您的确切问题，在链接的问题中，范围是不同的，没有共同部分，并且搜索范围可能跨越多个范围。如果您的问题相同，则非常容易：
将范围数组按其最低值排序（因为它们不重叠，所以这也是按其上限值排序的相同顺序）。现在只需对目标下限值进行二进制搜索（如果不是精确匹配，则较小），并对目标上限值进行一次二进制搜索（如果不是精确匹配，则更大）。结果索引是覆盖的范围。您必须检查索引处的范围是包含还是排除的，但这只是2个检查。总体复杂度为O（log n）。
听起来你需要一个实现SortedSet接口的类。TreeSet是核心API附带的实现。
有一个集合按最低值排序，另一个按最高值排序。
然后，您可以使用内存集合实现等效于数据库算法的功能。
至于这是否比O(n)更快，我无法确定。
就像四叉树适用于一组二维点一样，一个简单的二叉树应该适用于这种情况。用你的范围构建一棵树。
进一步解释： 树中的每个节点都包含两个整数，即范围的开始和结束，以及两个子节点（如果它不是叶节点）。 要找到您的输入范围跨越的范围，则从树的顶部开始。
- if the node range intersects the input range:
- if it's a leaf node, then add the range to your result list
- if it's not a leaf node, then traverse down to the child nodes and repeat this process.
应该是O(logN)
更多细节： 二叉树的结构类似于四叉树的一维版本。每个节点都有三个整数（抱歉我之前说了两个，但现在我意识到你需要三个），最低的表示低于此节点的最低范围的最低值，最高的表示低于此节点的最高范围的最高值，以及中心点。左子节点将从此节点的最低点延伸到其中心点。右子节点将从此节点的中心点延伸到其最高点。如果只有一个范围从“最低”到“最高”，则不需要中心点，这将是一个叶子节点。理想情况下，您会选择每个节点的中心点以保持树的平衡。
final int lower; // lower end of range
final int upper; // upper end of range
public int compareTo(Object obj) {
if(obj==null) { return -1; }
Range oth=(Range)obj;
if(lower<oth.lower) { return -1; }
if(lower>oth.lower) { return 1; }
if(upper<oth.upper) { return -1; }
if(upper>oth.upper) { return 1; }
return 0;
}
范围插入：
public Builder addRange(int fir, int las) {
if(fir!=-1) { fir&=0x001FFFFF; }
if(las!=-1) { las&=0x001FFFFF; }
if(codepoints==null || codepoints.length==0) {
codepoints=new Range[]{new Range(fir,las)};
}
else {
int idx=Range.findChar(codepoints,fir);
int ins=(idx<0 ? -(idx+1) : idx);
if(idx<0) {
if (ins>0 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); } // new range adjoins the following range (can't overlap or idx would be >=0)
else if(ins<codepoints.length && las>=(codepoints[ins ].lower-1)) { idx=ins; } // new range overlaps or adjoins the following range
}
if(idx<0) {
codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
}
else {
boolean rmv=false;
for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
codepoints[xa]=null;
rmv=true;
}
if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
}
if(rmv) { codepoints=Range.removeNulls(codepoints); }
}
}
return this;
}
二分查找：
static int findChar(Range[] arr, int val) {
if(arr.length==1) {
if (val< arr[0].lower) { return -1; } // value too low
else if(val<=arr[0].upper) { return 0; } // value found
else { return -2; } // value too high
}
else {
int lowidx=0; // low index
int hghidx=(arr.length-1); // high index
int mididx; // middle index
Range midval; // middle value
while(lowidx<=hghidx) {
mididx=((lowidx+hghidx)>>>1);
midval=arr[mididx];
if (val< midval.lower) { hghidx=(mididx-1); } // value too low
else if(val<=midval.upper) { return mididx; } // value found
else { lowidx=(mididx+1); } // value too high
}
return -(lowidx+1); // value not found.
}
}