Вычесть перекрытия между двумя диапазонами без наборов

NO SETS!

Я не могу использовать наборы, потому что:

• Диапазоны будут слишком длинными.
• Они будут занимать слишком много памяти.
• Создание самих наборов займет слишком много времени.

Использование только конечных точек диапазонов, существует ли оптимальный способ вычесть два списка диапазонов?

Пример:

r1 = (1, 1000), (1100, 1200)  
r2 = (30, 50), (60, 200), (1150, 1300)

r1 - r2 = (1, 29), (51, 59), (201, 1000), (1100, 1149)

Дополнительная информация:

• r2 не должен перекрывать r1
• r1 и r2 не будут иметь пар, которые перекрывают другие пары. Например, в r1 не будет одновременно (0,30) и (10, 25)

Спасибо.