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

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)

Answer 2

Sort all the points. Then go through the list incrementing a counter for "start" points, and decrementing it for "end" points. If the counter reaches 0, then it really is an endpoint of one of the intervals in the union.

The counter will never go negative, and will reach 0 at the end of the list.

Answer 3

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