Алгоритм получения разности двух наборов интервалов

Задача

Предположим, у меня есть два набора интервалов с именами A и B. Как мне найти разницу (относительное дополнение )наиболее эффективным способом по времени -и памяти -?

Картинка для иллюстрации:

Конечными точками интервала являются целые числа(≤ 2 ¹²⁸-1 ), и они всегда имеют длину 2 ⁿ и выровнены по решетке m×2 ⁿ (, так что вы можете составить из них бинарное дерево ).

Интервалы могут перекрываться во входных данных, но это не влияет на выходные данные (результат при сглаживании будет таким же ).

Проблема в том, что в обеих коллекциях МНОГО интервалов (вплоть до 100 000 000 ), поэтому наивные реализации, вероятно, будут медленными.

Входные данные считываются из двух файлов и сортируются таким образом, что меньшие вложенные -интервалы (, если они перекрываются ), идут сразу после своих родителей в порядке их размера. Например:

[0,7]
[0,3]
[4,7]
[4,5]
[8,15]
...

Что я пробовал?

Уже,Я работал над реализацией, которая генерирует бинарное дерево поиска, при этом объединяя соседние интервалы ([0,3],[4,7] => [0,7]). из обеих коллекций, затем проходит по второму дереву и "выталкивает" интервалы, которые присутствуют в обоих (, подразделяя большие интервалы в первом дереве, если это необходимо ).

Хотя это, кажется, работает для небольших коллекций, для хранения самого дерева требуется все больше и больше оперативной памяти, не говоря уже о времени, необходимом для завершения вставки и удаления из дерева.

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

Итак, как мне решить эту проблему эффективным способом?

Отказ от ответственности:Это не домашнее задание, а модификация/обобщение реальной -жизненной проблемы, с которой я столкнулся. Я программирую на C++, но могу принять алгоритм на любом [императивном] языке.