Как я могу найти максимальный интервал длины, который является суммой открытых интервалов? C / C ++

Question

Моя проблема:

Вам дан массив из n элементов: struct Interval {int x; int y}; Элементы этого массива являются открытыми интервалами. Я должен найти интервалы T (или меньше), сумма которых соответствует максимальному интервалу длины.

Я подумал об использовании дерева интервалов, но понятия не имею, как решить проблему.

Answer 1

Сортировка (по значению) всех точек границы интервала по значению вместе с ключом +1/-1, обозначающим начало и конец интервалов (в случае связующего счета для значения ключа: -1 до +1 для открытых интервалов)

Марка ActiveCount = 0
Пройдитесь по отсортированному списку, увеличивая ActiveCount на значение ключа.

Когда ActiveCount становится ненулевым, объединение интервалов начинается, когда оно становится нулевым - объединение интервалов заканчивается. Найдите самую длинную разницу в конце.

Для вашего примера (частично):

(0;3), (1;4), (5;7), (2;3)
make pairs 
(0, 1), (3,-1), (1, 1), (4, -1), (5,1), (7,-1), (2,1), (3,-1)
sorted 
(0, 1), (1, 1), (2,1), (3,-1), (3,-1), (4, -1), (5,1), (7,-1)
ActiveCount
 1       2       3     2        1       0        1     0
 ^                                      ^
 start                                  end