我有一系列不能重叠的时间间隔（t_start，t_end），即：t_end(i) > t_start(i+1)。我想做以下操作：
1) 添加新的（并集）区间 [ {(1,4),(8,10)} U (3,7) = {(1,7),(8,10)} ]
2) 取出区间 [ (1,7) - (3,5) = {(1,3),(5,7)}
3) 检查一个点或一个区间是否与我的系列中的一个区间重叠 (intersection)
4) 找到第一个"在某个点之后的最小长度的“非间隔”[{(1,4),(7,8)}：在 4 和 7 之间有一个长度为 3 的“非间隔”]。
我想知道实现这一点的好方法，复杂性低（所有操作的 log n 都可以）。
相关问题：快速时间间隔查找的数据结构
听起来您可以只使用所有边界时间的平衡二叉树。
例如，将 {(1,4), (8,10), (12,15)} 表示为包含 1、4、8、10、12 和 15 的树。
每个节点都需要说明它是间隔的开始还是结束。所以：
8 (start)
/ \
1 (start) 12 (start)
\ / \
4 (end) 10 (end) 15 (end)
（这里所有的“结束”节点巧合地都在底部。）
然后我认为您可以在 O(log n) 时间内完成所有操作。添加间隔：
找到开始时间。如果它已经在树中作为开始时间，您可以将它留在那里。如果它已经在树中作为结束时间，您将要删除它。如果它不在树中并且在现有时间间隔内没有下降，您将需要添加它。否则你不想添加它。
找到停止时间，使用相同的方法找出是否需要添加、删除或不需要。
现在您只想添加或删除上述启动和停止节点，同时删除其间的所有现有节点。为此，您只需在树中的这两个位置处或正上方重建树节点。如果树的高度是 O(log n)，你可以通过使用平衡树来保证，这需要 O(log n) 时间。
（免责声明：如果您使用 C++ 并进行显式内存管理，那么您最终可能会释放超过 O(log n) 块内存，但实际上释放节点所需的时间应该由任何人计费添加它，我想。）
删除间隔大致相同。
检查一个点或间隔很简单。
在给定时间后找到至少给定大小的第一个间隙也可以在 O(log n) 中完成，如果您还为每个节点缓存另外两条信息：
在每个开始节点（最左边除外）中，间隙的大小紧靠左边。
在每个节点中，出现在该子树中的最大间隙的大小。
要找到在给定时间之后出现的给定大小的第一个间隙，首先在树中找到该时间。然后向上走，直到到达一个声称包含足够大间隙的节点。如果你从右边上来，你知道这个缺口在左边，所以你忽略它，继续往上走。否则你是从左边来的。如果该节点是起始节点，请检查其左侧的间隙是否足够大。如果是这样，你就完成了。否则，足够大的间隙必须在右边的某个地方。向右走，然后继续向下，直到找到间隙。同样，因为树的高度是 O(log n)，所以遍历它 3 次（向下、向上和可能再次向下）是 O(log n)。
在不知道更多细节的情况下，我建议阅读有关Interval Trees的内容。区间树是更通用的kd-trees的特殊一维案例，具有O(n log n)构建时间和O(log n)典型操作时间。您需要自己找到确切的算法实现，但您可以从CGAL开始。
我知道您已经接受了答案，但是由于您表示您可能会在 C++ 中实现，您还可以查看 Boosts Interval Container Library ( http://www.boost.org/doc/libs/1_46_1 /libs/icl/doc/html/index.html）。
我使用 AVL 树的区间树实现。
public class IntervalTreeAVL<T>{
private static class TreeNode<T>{
private T low;
private T high;
private TreeNode<T> left;
private TreeNode<T> right;
private T max;
private int height;
private TreeNode(T l, T h){
this.low=l;
this.high=h;
this.max=high;
this.height=1;
}
}
private TreeNode<T> root;
public void insert(T l, T h){
root=insert(root, l, h);
}
private TreeNode<T> insert(TreeNode<T> node, T l, T h){
if(node==null){
return new TreeNode<T>(l, h);
}
else{
int k=((Comparable)node.low).compareTo(l);
if(k>0){
node.left=insert(node.left, l, h);
}
else{
node.right=insert(node.right, l, h);
}
node.height=Math.max(height(node.left), height(node.right))+1;
node.max=findMax(node);
int hd = heightDiff(node);
if(hd<-1){
int kk=heightDiff(node.right);
if(kk>0){
node.right=rightRotate(node.right);
return leftRotate(node);
}
else{
return leftRotate(node);
}
}
else if(hd>1){
if(heightDiff(node.left)<0){
node.left = leftRotate(node.left);
return rightRotate(node);
}
else{
return rightRotate(node);
}
}
else;
}
return node;
}
private TreeNode<T> leftRotate(TreeNode<T> n){
TreeNode<T> r = n.right;
n.right = r.left;
r.left=n;
n.height=Math.max(height(n.left), height(n.right))+1;
r.height=Math.max(height(r.left), height(r.right))+1;
n.max=findMax(n);
r.max=findMax(r);
return r;
}
private TreeNode<T> rightRotate(TreeNode<T> n){
TreeNode<T> r = n.left;
n.left = r.right;
r.right=n;
n.height=Math.max(height(n.left), height(n.right))+1;
r.height=Math.max(height(r.left), height(r.right))+1;
n.max=findMax(n);
r.max=findMax(r);
return r;
}
private int heightDiff(TreeNode<T> a){
if(a==null){
return 0;
}
return height(a.left)-height(a.right);
}
private int height(TreeNode<T> a){
if(a==null){
return 0;
}
return a.height;
}
private T findMax(TreeNode<T> n){
if(n.left==null && n.right==null){
return n.max;
}
if(n.left==null){
if(((Comparable)n.right.max).compareTo(n.max)>0){
return n.right.max;
}
else{
return n.max;
}
}
if(n.right==null){
if(((Comparable)n.left.max).compareTo(n.max)>0){
return n.left.max;
}
else{
return n.max;
}
}
Comparable c1 = (Comparable)n.left.max;
Comparable c2 = (Comparable)n.right.max;
Comparable c3 = (Comparable)n.max;
T max=null;
if(c1.compareTo(c2)<0){
max=n.right.max;
}
else{
max=n.left.max;
}
if(c3.compareTo((Comparable)max)>0){
max=n.max;
}
return max;
}
TreeNode intervalSearch(T t1){
TreeNode<T> t = root;
while(t!=null && !isInside(t, t1)){
if(t.left!=null){
if(((Comparable)t.left.max).compareTo(t1)>0){
t=t.left;
}
else{
t=t.right;
}
}
else{
t=t.right;
}
}
return t;
}
private boolean isInside(TreeNode<T> node, T t){
Comparable cLow=(Comparable)node.low;
Comparable cHigh=(Comparable)node.high;
int i = cLow.compareTo(t);
int j = cHigh.compareTo(t);
if(i<=0 && j>=0){
return true;
}
return false;
}
}
我刚刚发现Guava 的 Range和RangeSet正是这样做的。
它实现了引用的所有操作：
联盟
RangeSet<Integer> intervals = TreeRangeSet.create();
intervals.add(Range.closedOpen(1,4)); // stores {[1,4)}
intervals.add(Range.closedOpen(8,10)); // stores {[1,4), [8,10)}
// Now unite 3,7
intervals.add(Range.closedOpen(3,7)); // stores {[1,7), [8,10)}
减法
intervals.remove(Range.closedOpen(3,5)); //stores {[1,3), [5, 7), [8, 10)}
路口
intervals.contains(3); // returns false
intervals.contains(5); // returns true
intervals.encloses(Range.closedOpen(2,4)); //returns false
intervals.subRangeSet(Range.closedOpen(2,4)); // returns {[2,3)} (isEmpty returns false)
intervals.subRangeSet(Range.closedOpen(3,5)).isEmpty(); // returns true
寻找空白空间（这将与最坏情况下的集合迭代具有相同的复杂性）：
Range freeSpace(RangeSet<Integer> ranges, int size) {
RangeSet<Integer> frees = intervals.complement().subRangeSet(Range.atLeast(0));
for (Range free : frees.asRanges()) {
if (!free.hasUpperBound()) {
return free;
}
if (free.upperEndpoint() - free.lowerEndpoint() >= size) {
return free;
}
}