Union of Intervals

Use the sweep line algorithm. Basically, you sort all the values in a list (while keeping whether it's beginning or end of the interval along with each item). This operation is O(n log n). Then you loop in a single pass along the sorted items and compute the intervals O(n).

O(n log n) + O(n) = O(n log n)

Sort them by one of the terms (start, for example), then check for overlaps with its (right-hand) neighbor as you move through the list.

class tp:
    def __repr__(self):
        return "(%d,%d)" % (self.start, self.end)

    def __init__(self, start, end):
        self.start = start
        self.end = end


s = [tp(5, 10), tp(7, 8), tp(0, 5)]
s.sort(key=lambda self: self.start)
y = [s[0]]
for x in s[1:]:
    if y[-1].end < x.start:
        y.append(x)
    elif y[-1].end == x.start:
        y[-1].end = x.end