Точка максимального перекрытия

Question

Предположим, что мы хотим отслеживать точку максимального перекрытия в наборе интервалов - точку, которая имеет наибольшее количество интервалов в базе данных, перекрывающих ее.

a. Покажите, что всегда будет точка максимального перекрытия, которая является конечной точкой одного из сегментов.

b. Создайте структуру данных, которая эффективно поддерживает операции INTERVAL-INSERT, INTERVAL-DELETE и FIND-POM, которые возвращают точку максимального перекрытия. (Подсказка: держите красно-черное дерево всех конечных точек. Свяжите значение +1 с каждой левой конечной точкой и сопоставьте значение -1 с каждой правой конечной точкой. Увеличьте каждый узел дерева с помощью дополнительной информации, чтобы поддерживать точка максимального перекрытия.)

эта проблема находится в книге введение в алгоритм. Но я не знаю, как решить второй вопрос. если у большего ума есть изящное решение, пожалуйста, поделитесь своей идеей со мной! Благодарю.

Answer 1

цитата: http://ripcrixalis.blog.com/2011/02/08/clrs-chapter-14/

Держите RB-дерево всех конечных точек. Вставляем конечные точки один за другим в качестве развертки, просматривая слева направо. С каждой левой конечной точкой e свяжите значение p [e] = +1 (увеличивая перекрытие на 1). С каждой правой конечной точкой e свяжите значение p [e] = -1 (уменьшая перекрытие на 1). Когда несколько конечных точек имеют одинаковое значение, вставьте все левые конечные точки с этим значением, прежде чем вставлять любые правые конечные точки с этим значением.

Вот несколько интуиций. Пусть e1, e2,. , , , en - отсортированная последовательность конечных точек, соответствующих нашим интервалам. Обозначим через s (i, j) сумму p [ei] + p [ei + 1] + ··· + p [ej] для 1 ≤ i ≤ j ≤ n. Мы хотим найти i максимизирующее s (1, i). Каждый узел x хранит три новых атрибута. Мы храним v [x] = s (l [x], r [x]), сумму значений всех узлов в поддереве x. Мы также сохраняем m [x], максимальное значение, полученное выражением s (l [x], i) для любого i. Мы сохраняем o [x] как значение i, для которого m [x] достигает своего максимума. Для часового мы определяем v [nil [T]] = m [nil [T]] = 0.

Мы можем вычислить эти атрибуты снизу вверх, чтобы удовлетворить требованиям теоремы 14.1:

v[x] = v[left[x]] + p[x] + v[right[x]] , 
m[x] = max{ 
m[left[x]] (max is in x’s left subtree), 
v[left[x]] + p[x] (max is at x), 
v[left[x]] + p[x] + m[right[x]] (max is in x’s right subtree). } 

Как только мы поймем, как вычислить m [x], легко вычислить o [x] из информации по x и двум ее детям.

FIND-POM: вернуть интервал, конечная точка которого представлена ​​o [корень [T]]. Из-за того, как мы определили новые атрибуты, в теореме 14.1 говорится, что каждая операция выполняется в O (lg n) времени. Фактически FIND-POM занимает только время O (1).