Найти общие элементы из заданных интервалов

Question

Я пытаюсь решить эту проблему, где мне нужно найти общие элементы из данных интервалов. Например, в интервалах [1,5], [2, 8], [3, 4] общими элементами из всех интервалов будут [3, 4]. Каков наилучший способ реализовать это в C ++. Я попытался реализовать это с помощью std :: set_intersection. Но для этих двух работ мне нужно заполнить другой вектор, содержащий элементы внутри интервала, а затем найти пересечение между ними, которое не разрешено из-за ограниченного пространства. Есть ли другой способ сделать это?

Answer 1

Пересечение N интервалов [x ₁ , y ₁ ], [x ₂ , y ₂ ] ... [x _N , y _N ] определяется диапазоном [max (x ₁ , x ₂ ), ..., x _N ), мин (y ₁ , y ₂ , ..., y _N )]. Это может быть доказано математической индукцией и занимает время O ( N ). Вы можете прочитать больше об интервальной арифметике здесь .

Примечание : Если мы получим окончательный диапазон как [x, y], где x> y, то диапазон будетпустой.

Answer 2

Звучит так, будто вы ищете Дерево интервалов.

В информатике дерево интервалов - это древовидная структура данных для хранения интервалов. В частности, он позволяет эффективно находить все интервалы, которые перекрываются с любым заданным интервалом или точкой. Он часто используется для оконных запросов, например, чтобы найти все дороги на компьютеризированной карте внутри прямоугольного видового экрана или найти все видимые элементы в трехмерной сцене. Аналогичная структура данных - дерево сегментов.