Нахождение перекрытия между несколькими интервалами

Question

Допустим, у меня есть список интервалов (или диапазонов) (например, 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 отдельных дерева интервалов, чтобы выяснить это. Есть лучший способ сделать это?

Answer 1

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

{
  int range;
  int intervalFrom;
  int intervalTo;
}

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

Answer 2

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