Let's say I have the following interval, stored as a list:

main_iv = [10, 30]

and the following intervals which interrupt (overlap) the interval above:

break_iv = [[8, 12], [15, 18], [32, 40], [42, 43]]

I would like to extend main_iv until it has reached its original length entirely (20), again taking into acount any interruptions that occur during the extension.

I have working code for the first interruption but I really struggle to find a way to make this work continously and dynamically for an unspecified amount of interruptions.

def overlap_calc(start_1, start_2, end_1, end_2):
        latest_start = max(start_1, start_2)
        earliest_end = min(end_1, end_2)
        delta = (earliest_end - latest_start)   1
        overlap = max(0, delta)
        return(overlap)

main_iv = [10, 30]

break_iv = [[8, 12], [15, 18], [32, 40]]

overlap = 0
for sub_iv in break_iv:
    overlap  = overlap_calc(main_iv[0], sub_iv[0], main_iv[1], sub_iv[1])

main_iv[1] = main_iv[1]   overlap

print(main_iv)

This gives the following output, which takes into account the overlap [8, 12] (overlap of 3) and [15, 18] (overlap of 4):

[10, 37]

However, taking into acount the interval [32, 40] again overlapping with the extension (running from 31 to 37), the original interval can only be completed after 40. The indended output would therefore look like this:

[10, 46]

CodePudding user response：

If I understand your problem correctly, you could do something like this.

def solve(main, gaps):
    start, end = main
    for lo, hi in gaps:
        if hi < start:
            # gap is lower than main
            continue
        if lo > end:
            # gap is higher than main
            break
        # extend main end by overlap length
        overlap_length = hi   1 - max(lo, start)
        end  = overlap_length
        
    return [start, end]

This gives the expected result, assuming that there are no overlaps between the gaps, and the gaps are in ascending order.

>>> solve(main=(10,30), gaps=[(8,12), (15,18), (32,40)])
[10, 46]