Максимальное перекрытие интервалов с использованием дерева интервалов [closed]

В его нынешнем виде этот вопрос не подходит для нашего формата вопросов и ответов. Мы ожидаем, что ответы будут подтверждены фактами, ссылками или опытом, но этот вопрос, скорее всего, повлечет за собой дебаты, аргументы, опросы или расширенное обсуждение. Если вы считаете, что этот вопрос можно улучшить и, возможно, снова открыть, посетите справочный центр , чтобы получить рекомендации.

Закрыт 7 лет назад .

Вот интересный вопрос: учитывая набор из N интервалов ([начало, конец]), используйте дерево интервалов, чтобы найти максимальное количество перекрывающихся интервалов.

аналогичный вопрос на StackOverflow предоставил решение O (N), но если мы сможем предварительно обработать интервалы в дерево интервалов, возможно, мы сможем найти решение за логарифмическое время.

Фактически, задача упражнений в книге «Введение в алгоритмы» Кормена и др. Предполагает, что это возможно путем увеличения красно-черного дерева интервалов. Есть идеи, как это можно сделать?

algorithm interval-tree

задан Community 23 May 2017 в 12:16

0 ответов

Другие вопросы по тегам:

algorithm interval-tree

Максимальное перекрытие интервалов с использованием дерева интервалов [closed]

0 ответов

Похожие вопросы: