algorithm - Python interval interesction

Question

My problem is as follows:

having file with list of intervals:

1 5
2 8
9 12
20 30

And a range of

0 200

I would like to do such an intersection that will report the positions [start end] between my intervals inside the given range.

For example:

8 9
12 20
30 200

Beside any ideas how to bite this, would be also nice to read some thoughts on optimization, since as always the input files are going to be huge.

Answer 1

this solution works as long the intervals are ordered by the start point and does not require to create a list as big as the total range.

code

with open("0.txt") as f:
    t=[x.rstrip("
").split("") for x in f.readlines()]
    intervals=[(int(x[0]),int(x[1])) for x in t]

def find_ints(intervals, mn, mx):
    next_start = mn
    for x in intervals:
        if next_start < x[0]:
            yield next_start,x[0]
            next_start = x[1]
        elif next_start < x[1]:
            next_start = x[1]
    if next_start < mx:
        yield next_start, mx

print list(find_ints(intervals, 0, 200))

output:

(in the case of the example you gave)

[(0, 1), (8, 9), (12, 20), (30, 200)]