Range (Interval) Intersection

range_union.py

def unionRanges(intervals):
    intervals = sorted(intervals) # Sort by elem[0]
    ranges = [ ]
    if len(intervals) == 0:
        return [ ]
    start = intervals[0][0]
    end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] < end:
            end = max(end, intervals[i][1])
        else:
            ranges.append((start, end))
            start = intervals[i][0]
            end = intervals[i][1]
    ranges.append((start, end))
    return ranges
            
# Right end-point of interval isn't included in the interval
intervals = [ # Single range
              (10, 15),
              # 2 Ranges which overlap in both directions
              (15, 20), (17, 22),
              # One big range contains all others
              (100, 200), (110, 190), (120, 180),
              # Keep extending the interval to the right
              (200, 250), (210, 260), (220, 300),
              # 3 Ranges, with only 2 of them intersecting
              # at any point in time
              (310, 330), (320, 340), (330, 350),
            ]

print unionRanges(intervals)

# Prints:
# [(10, 15), (15, 22), (100, 200), (200, 300), (310, 350)]