Union of intervals

Question

I've got a class representing an interval. This class has two properties "start" and "end" of a comparable type. Now I'm searching for an efficient algorithm to take the union of a set of such intervals.

Thanks in advance.

Answer 1

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