Subtract Overlaps Between Two Ranges Without Sets

NO SETS!

I can't use Sets because:

• The ranges will be too long.
• They will take up too much memory
• The creation of the sets themselves will take too long.

Using only the endpoints of the of the ranges, is there an optimal way to subtract two lists of ranges?

Example:

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

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

Other info:

• r2 does not have to overlap r1
• r1 and r2 will not have pairs that overlap other pairs. For instance, r1 will not have both (0,30) and (10, 25)

Thanks.

The interval package may provide all that you need.

from interval import Interval, IntervalSet
r1 = IntervalSet([Interval(1, 1000), Interval(1100, 1200)])
r2 = IntervalSet([Interval(30, 50), Interval(60, 200), Interval(1150, 1300)])
print(r1 - r2)

>>> [1..30),(50..60),(200..1000],[1100..1150)