CODEWITHSUNDEEP
pythonintervals
Chickenmarkus
Chickenmarkus

Reputation: 1161

Combine two sets of intervals to one set of intervals

I have two ordered sets of intervals (( means "start" and ) means "stop"):

      1: (          )              (          )
         0---1------3------5---6---7------9---10----> time
      2: (   )(            )   (          )

In two list it would look like:

intervals1 = [(0,3), (7,10)]
intervals2 = [(0,1), (1,5), (6,9)]

The further evaluation of the time series will be an integration over time of both. For that, I would like to keep the interval character but as common intervals. In the given example, the time series and corresponding list would look like:

common: (   )(     )(     )   (   )(     )(  )
        0---1------3------5---6---7------9---10----> time
intervals = [(0,1), (1,3), (3,5), (6,7), (7,9), (9,10)]

How can I combine these two time series efficiently?

Upvotes: 1

Views: 681

Answers (1)

Blckknght
Blckknght

Reputation: 104712

I think you can efficiently solve this issue with a stack based algorithm, since you know that no more than two intervals can overlap at any given position:

def merge_intervals(a, b):
    stack = sorted(a+b, reverse=True)

    while len(stack) > 1:
        first = stack.pop()
        second = stack.pop()
        if first == second:         # identical intervals can be merged
            yield first
        elif first[1] <= second[0]: # no overlapping, yield first interval, put back second
            yield first
            stack.append(second)
        elif first[0] == second[0]: # overlap at start, yield shorter, put back rest of longer
            if first[1] > second[1]:
                first, second = second, first
            yield first
            stack.append((first[1], second[1]))
        elif first[1] < second[1]:  # partial overlap, yield first two parts, put back rest
            yield first[0], second[0]
            yield second[0], first[1]
            stack.append((first[1], second[1]))
        else: # first[1] >= second[1] # total envelopment
            yield first[0], second[0]
            yield second
            if first[1] != second[1]:
                stack.append((second[1], first[1]))

    yield from stack # there may or may not be one element left over

This is a generator, so you'll get your desired output with:

intervals = list(merge_intervals(intervals1, intervals2))

Upvotes: 2

Related Questions