0

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]
quadratecode
  • 396
  • 1
  • 2
  • 12
  • 3
    I am unclear what you would like `main_iv` to look like at the end of this process. Can you update your question to provide an explicit example? – larsks May 27 '22 at 13:18
  • @larsks Aplogies for not being precise enough. have amended my question with the intended output (manually evaluated, but should be correct). – quadratecode May 27 '22 at 13:24
  • 1
    Are the breaks always discrete and ordered, or could they overlap each other or come out of sequence? – Håken Lid May 27 '22 at 13:52
  • @HåkenLid For my use case, they will always be discrete and ordered. – quadratecode May 27 '22 at 14:37

1 Answers1

1

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]
Håken Lid
  • 22,318
  • 9
  • 52
  • 67
  • Brilliant, thank you so much! For anyone coming across this and looking to merge overlaps before passing them on, I have adressed this [here](https://stackoverflow.com/a/72397132/14819955) – quadratecode May 27 '22 at 15:07