[ACCEPTED]-Data structure for handling intervals-intervals

It sounds like you could just use a balanced binary tree of 53 all the boundary times.

For example, represent 52 {(1,4), (8,10), (12,15)} as a tree containing 51 1, 4, 8, 10, 12, and 15.

Each node needs 50 to say whether it's the start or end of 49 an interval. So:

                          8 (start)
                         /        \
                1 (start)         12 (start)
                      \             /      \
                     4 (end)   10 (end)   15 (end)

(Here all the "end" nodes 48 ended up at the bottom by coincidence.)

Then 47 I think you can have all your operations 46 in O(log n) time. To add an interval:

• Find the start time. If 45 it's already in the tree as a start time, you 44 can leave it there. If it's already in the 43 tree as an end time, you'll want to remove 42 it. If it's not in the tree and it doesn't 41 fall during an existing interval, you'll 40 want to add it. Otherwise you don't want 39 to add it.

• Find the stop time, using the 38 same method to find out if you need to add 37 it, remove it, or neither.

• Now you just want 36 to add or remove the abovementioned start 35 and stop nodes and, at the same time, delete 34 all the existing nodes in between. To do 33 this you only need to rebuild the tree nodes 32 at or directly above those two places in the tree. If the height 31 of the tree is O(log n), which you can guarantee 30 by using a balanced tree, this takes O(log 29 n) time.

(Disclaimer: If you're in C++ and 28 doing explicit memory management, you might 27 end up freeing more than O(log n) pieces 26 of memory as you do this, but really the 25 time it takes to free a node should be billed 24 to whoever added it, I think.)

Removing an interval is largely 23 the same.

Checking a point or interval is straightforward.

Finding the first gap of at least a given size after a given time can be done 22 in O(log n) too, if you also cache two more 21 pieces of information per node:

• In each start 20 node (other than the leftmost), the size 19 of the gap immediately to the left.

• In every 18 node, the size of the largest gap that appears 17 in that subtree.

To find the first gap of 16 a given size that appears after a given 15 time, first find that time in the tree. Then 14 walk up until you reach a node that claims 13 to contain a large enough gap. If you came 12 up from the right, you know this gap is 11 to the left, so you ignore it and keep walking 10 up. Otherwise you came from the left. If 9 the node is a start node, check to see if 8 the gap to its left is large enough. If 7 so, you're done. Otherwise, the large-enough 6 gap must be somewhere to the right. Walk 5 down to the right and continue down until 4 you find the gap. Again, because the height 3 of the tree is O(log n), walking it three 2 times (down, up, and possibly down again) is 1 O(log n).

Without knowing anymore specifics, I'd suggest 6 reading about Interval Trees. Interval trees are a special 5 1 dimensional case of more generic kd-trees, and 4 have a O(n log n) construction time, and O(log n) typical 3 operation times. Exact algorithm implementations 2 you'd need to find yourself, but you can 1 start by looking at CGAL.

I know you've already accepted an answer, but 4 since you indicated that you will probably 3 be implementing in C++, you could also have 2 a look at Boosts Interval Container Library 1 (http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html).

My interval tree implementation with AVL 1 tree.

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;
    }
}

I've just found Guava's Range and RangeSet which do exactly that.

It 3 implements all the operations cited:

1. Union

   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)}
   

2. Subraction

   intervals.remove(Range.closedOpen(3,5)); //stores {[1,3), [5, 7), [8, 10)}
   

3. Intersection

   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
   

4. Finding 2 empty spaces (this will be the same complexity 1 as a set iteration in the worst case):

   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;
           }
       }