オーバーラップできない一連の時間間隔 (t_start,t_end) があります。つまり、t_end(i) > t_start(i+1) です。次の操作を行いたいです。
1) 新しい (Union of) 区間を追加 [ {(1,4),(8,10)} U (3,7) = {(1,7),(8,10)} ]
2) 区間を取り出す [ (1,7) - (3,5) = {(1,3),(5,7)}
3) ポイントまたは区間がシリーズの区間と重複しているかどうかを確認する (交点)
4) 最初の "ある点の後の最小長の「非間隔」[ {(1,4),(7,8)}: 4 と 7 の間に長さ 3 の「非間隔」があります]。
複雑さの少ない、これを実装する良い方法を知りたいです（すべての操作のログ 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) 時間で実行できると思います。間隔を追加するには:
開始時間を見つけます。開始時刻としてすでにツリーにある場合は、そのままにしておくことができます。すでに終了時刻としてツリーにある場合は、削除する必要があります。ツリーに含まれておらず、既存の間隔に該当しない場合は、追加する必要があります。それ以外の場合は、追加したくありません。
同じ方法を使用して停止時間を見つけ、追加する必要があるか、削除する必要があるか、またはどちらも必要ないかを確認します。
ここで、上記の開始ノードと停止ノードを追加または削除し、同時に間にある既存のノードをすべて削除します。これを行うには、ツリー内のこれら 2 つの場所またはそのすぐ上にあるツリー ノードを再構築するだけです。ツリーの高さが O(log n) の場合、バランスのとれたツリーを使用して保証できますが、これには O(log n) の時間がかかります。
(免責事項: C++ で明示的なメモリ管理を行っている場合、これを行うと O(log n) 個を超えるメモリを解放することになる可能性がありますが、実際には、ノードを解放するのにかかる時間は誰にでも請求する必要があります追加したと思います。）
間隔の削除は、ほとんど同じです。
ポイントまたはインターバルのチェックは簡単です。
ノードごとにさらに2つの情報をキャッシュする場合、特定の時間後に少なくとも特定のサイズの最初のギャップを見つけることもO(log n)で実行できます。
各開始ノード (一番左以外) で、すぐ左にあるギャップのサイズ。
すべてのノードで、そのサブツリーに表示される最大ギャップのサイズ。
特定の時間の後に現れる特定のサイズの最初のギャップを見つけるには、まずツリーでその時間を見つけます。次に、十分な大きさのギャップが含まれていると主張するノードに到達するまで歩きます。右から上がってきた場合は、このギャップが左にあることがわかっているので、それを無視して歩き続けます。そうでなければ、あなたは左から来ました。ノードが開始ノードである場合は、左側のギャップが十分に大きいかどうかを確認します。もしそうなら、あなたは終わりです。それ以外の場合、十分な大きさのギャップは右側のどこかになければなりません。右に歩き、隙間が見つかるまで下ります。繰り返しますが、木の高さは O(log n) であるため、3 回 (下、上、場合によっては再び下) 歩くことは O(log n) です。
詳細を知らなくても、Interval Treesについて読むことをお勧めします。間隔ツリーは、より一般的なkd-treesの特別な 1 次元のケースであり、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;
}
}