CODEWITHSUNDEEP
pythontimeoverlapping
michael James
michael James

Reputation: 13

How to separate some overlapping time periods in python?

I have a list of different time periods, start and end, let's say :

[(0, 50), (40, 70), (60,100), (65, 105), (90, 120), (110, 150) ]

I need somehow to find overlapping timerange and assign these time periods into different layers, where there is no overlapping in each layer, for example for the list above result should be :

[(0, 50, 'layer 1'), (60,100, 'layer 1'), (110,150, 'layer 1'),
 (40,70, 'layer 2'), (90,120, 'layer 2'),
 (65,105, 'layer 3')]

Right now I have added a "+"/"-" sign to the start_time/end_time, then sort them. I am stuck to the next step.

Upvotes: 0

Views: 142

Answers (2)

Andrej Kesely
Andrej Kesely

Reputation: 195438

Another solution, using defaultdict:

from collections import defaultdict


def find_layer(start, end, layers):
    l = 0
    while layers[l] > start:
        l += 1
    layers[l] = end
    return l

lst = [(0, 50), (40, 70), (60,100), (65, 105), (90, 120), (110, 150)]

# assuming lst is already sorted
# lst = sorted(lst)
layers = defaultdict(int)

for start, end in lst:
    print(start, end, 'layer_{}'.format(find_layer(start, end, layers) + 1))

Prints:

0 50 layer_1
40 70 layer_2
60 100 layer_1
65 105 layer_3
90 120 layer_2
110 150 layer_1

Upvotes: 1

RichieV
RichieV

Reputation: 5183

One approach is to create a list to contain the different layers, and populate it with your tuples, dynamically creating a new layer when needed.

# sort the data if it is not already in the order we need
data = sorted(data, key=lambda x: x[1])
data = sorted(data, key=lambda x: x[0])

# build layers as a list of lists
# the outer list will contain the layer levels
# the inner list will contain the periods/tuples in each layer
layers = [[data[0] + ('layer 1',)]] # initialize layer 1
for period in data[1:]: # get one period at a time and find which layer is a good fit
    for lay, temp in enumerate(layers):
        if period[0] > temp[-1][1]:
            # period starts after current layer's last period's end
            # add third element to tuple and append to layer
            temp.append(period + (f'layer {lay + 1}',))
            break
    else:
        # did not find a layer that can hold current period, create a new layer
        layers.append([period + (f'layer {len(layers) + 1}',)])

# flatten layers
layers = [e for L in layers for e in L]

Output

[(0, 50, 'layer 1'), (60, 100, 'layer 1'), (110, 150, 'layer 1'), (40, 70, 'layer 2'), (90, 120, 'layer 2'), (65, 105, 'layer 3')]

Upvotes: 0

Related Questions