7
Вот интересный вопрос: учитывая набор из N интервалов ([начало, конец]), используйте дерево интервалов, чтобы найти максимальное количество перекрывающихся интервалов.Максимальное перекрытие интервалов с использованием дерева интервалов
A similar question В StackOverflow предусмотрено решение O (N), но если мы можем предварительно обработать интервалы в дереве интервалов, возможно, мы сможем найти решение в логарифмическом времени.
На самом деле проблема упражнений в книге «Введение в алгоритмы» Кормена и др. Предполагает, что это возможно, увеличивая дерево красных черных интервалов. Любые идеи, как это можно сделать?
Вас интересуют такие операции, как 'Add (x, y) - добавить интервал к дереву',' Query() - найти максимальное количество перекрывающихся интервалов?? Вы также хотите, чтобы 'Del (x, y) - удалить интервал [x, y] из дерева'? – IVlad
Если интервалы расположены в дереве с сбалансированным интервалом, таком как тот, который указан в книге Кормена, мы уже знаем, что в O (lg N) время выполняются Add (interval) и Delete (interval). Поэтому я хотел бы знать, как использовать это дерево, чтобы найти максимальное количество перекрывающихся интервалов в предпочтительном O (lg N) времени. – stackoverflowuser2010
Можете ли вы определить перекрытие? То есть, вы имеете в виду набор интервалов с общей точкой или вы имеете в виду набор интервалов, так что между любыми парами существует пересекающийся путь? – Rafe