How to separate some overlapping time periods in python?

Question

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.

Answer 1

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