Структура данных для обработки интервалов

Похоже, вы могли бы просто использовать сбалансированное двоичное дерево всех граничных времен.

Например, представьте {(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 (журнал n), если вы также кэшируете еще две части информации на узел:

• В каждом начальном узле (кроме крайнего левого) размер зазора сразу слева.

• В каждом узле - размер наибольшего разрыва, который появляется в этом поддереве.

Чтобы найти первый пробел заданного размера, который появляется через заданное время, сначала найдите это время в дереве. Затем идите вверх, пока не дойдете до узла, который утверждает, что содержит достаточно большой промежуток. Если вы подошли справа, вы знаете, что эта пропасть находится слева, поэтому вы игнорируете ее и продолжаете идти вверх. В противном случае вы пришли слева. Если узел является начальным, проверьте, достаточно ли велик зазор слева от него. Если так, то все готово. В противном случае достаточно большой зазор должен быть где-то справа. Пройдите вправо и продолжайте идти, пока не найдете брешь. Опять же, поскольку высота дерева равна O (log n), пройти его три раза (вниз, вверх и, возможно, снова вниз) будет O (log n).

Не зная подробностей, я предлагаю прочитать о деревьях интервалов. Деревья интервалов представляют собой особый одномерный случай более общих kd-деревьев и имеют O(n log n) время строительства и O(log n) типичное время работы. Вам нужно будет найти точные реализации алгоритма, но вы можете начать с просмотра CGAL.

Я знаю, что вы уже приняли ответ, но поскольку вы указали, что, вероятно, будете реализовывать его на C ++, вы также можете взглянуть на библиотеку контейнеров Boosts Interval (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;
    }
}

Я только что нашел диапазон Гуавы и RangeSet, которые делают именно это.

Он реализует все перечисленные операции:

1. Союз

   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. Субракция

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

3. Пересечение

   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. Поиск пустых пространств (в худшем случае это будет такая же сложность, как и итерация по установке):

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