Поиск перекрытия среди нескольких интервалов

Допустим, у меня есть список интервалов (или диапазонов) (например, 10-15, 5-7, 9-12...). Проблема состоит в том, чтобы найти подмножество диапазонов, которые перекрываются. Конечно, для этого я могу использовать дерево интервалов.

Фактическая проблема, которая у меня есть, заключается в том, что существует несколько диапазонов. Лучше всего объяснить на примере:

  1. 10-15, 5-7, 9-12
  2. 1-2, 3-6, 14-15
  3. 3-5, 9-15, 10-15

В приведенном выше случае имеется перекрытие между (1) и (2) на втором диапазоне и между (3) и (1), (2) на третьем диапазоне.

По сути, мне нужно найти все перекрытия между списком элементов.

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


algorithm binary-tree interval-tree
person amit    schedule 17.03.2009    source источник
comment
Вы должны думать о том, что вы хотите/нужно. Вы хотите иметь диапазоны, которые перекрываются для всех 3, или все диапазоны, которые перекрываются между любыми двумя из них? Последнее приведет ко многим результатам, особенно для более чем 3 пунктов.   -  person schnaader    schedule 17.03.2009

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете построить только одно дерево интервалов со всеми интервалами. Вам просто нужно отслеживать, к какому диапазону принадлежал интервал, например:

{
  int range;
  int intervalFrom;
  int intervalTo;
}

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

person Seb    schedule 17.03.2009

arrow_upward
0
arrow_downward

Интервалы [a0, b0] и [a1, b1] перекрываются тогда и только тогда, когда min(b1,b0) > max(a1,a0)

person Devashish Das    schedule 20.04.2016
comment
Добро пожаловать в Stack Overflow! Хотя теоретически это может ответить на вопрос, было бы предпочтительнее включить сюда основные части ответа и предоставить ссылку для справки . - person Enamul Hassan; 20.04.2016