Есть два множества на числовой оси, хранящиеся в виде упорядоченного списка интервалов (для сокращения требований к памяти).

Пример:

мн-во A: интервал11(10-20) интервал12(20-30) интервал13(30-40)

и

мн-во B: интервал11(15-25) интервал12(28-29) интервал13(45-80)



Нужен алгоритм нахождения пересечения этих множеств.
Самое простое приходит в голову быстро:
(A + B) — (A — B) — (B — A)
где + операция объединения множеств, и — операция вычитания.
Этот алгоритм медленный и требует хранения двух дополнительных временных множеств.

Хотелось бы что-нибудь быстрое, 2*log(N) — знаю, что это возможно, но не пойму, как сделать. Есть идеи, где искать? Гугл пока не помог...


.