Максимальное перекрытие интервалов при использовании дерева интервалов
Вот интересный вопрос: учитывая набор из N интервалов ([начало, конец]), используйте дерево интервалов, чтобы найти максимальное количество перекрывающихся интервалов.
Аналогичный вопрос о Stackru предоставил решение O(N), но если мы сможем предварительно обработать интервалы в дереве интервалов, возможно, мы сможем найти решение в логарифмическом времени.
Фактически, проблема с упражнениями в книге "Введение в алгоритмы" Кормена и др. Предполагает, что это возможно путем увеличения красно-черного интервального дерева. Есть идеи, как это можно сделать?
2 ответа
Некоторый пример, чтобы посмотреть. Вы можете использовать интервальное дерево для этого. CGAL дает вам надежную реализацию для этого. Еще один интересный пример, похожий на вашу проблему.
Вы можете найти дерево интервалов на основе расширенного дерева самобалансировки AVL здесь: http://code.google.com/p/intervaltree/. это показывает вам, как это можно сделать. Вы можете сделать то же самое с красно-черным деревом.