2

If you have two pairs of values, start and end- how do you compute where their overlap is?

I.e if the pairs of start and end values are

[10, 20], [15, 20]

In this case compute_overlap((15,20),(10,20)) should return (15,20) because that is where the overlap is.

What is the best way to do this?

Rndm
  • 6,710
  • 7
  • 39
  • 58
The Unfun Cat
  • 29,987
  • 31
  • 114
  • 156
  • Perhaps this can help you out: http://stackoverflow.com/questions/5313374/how-to-overlap-intervals-efficiently/10895997#10895997 -- basically just search SO for python overlap and you have your answer. – Henrik Andersson Mar 08 '13 at 14:41
  • related to http://stackoverflow.com/questions/642763/python-intersection-of-two-lists I think – Oli Mar 08 '13 at 14:41
  • Searched so. No hits. Closest relative: http://stackoverflow.com/questions/2953967/built-in-function-for-computing-overlap-in-python – The Unfun Cat Mar 08 '13 at 14:44

3 Answers3

7

If your intervals are a, b and c, d, i.e.

(a, b), (c, d) = [10, 20], [15, 20]

then the overlapping interval is

x, y = max(a, c), min(b, d)
if x > y:  # no overlap
    x, y = None, None

and the amount of overlap is y - x or y - x + 1, depending on whether your intervals are closed or half-closed (assuming integers here).

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • Amount of overlap could also be `y - x - 1` if the first interval is half-closed at the higher end and the second interval is half-closed at the lower end, e.g. `[1,5)` and `(3,7]`. – G. Bach Mar 08 '13 at 16:17
  • @G.Bach: true, but intervals half-closed at the lower end, let alone a mix of interval types, are a bit "esoteric" -- if I had to work with them, I'd convert them to half-closed at the higher end if at all possible, then do any calculations. – Fred Foo Mar 09 '13 at 13:41
  • @larsmans Well if you're gonna convert anyway, if these are intervals on the integers, you may as well convert all of them to closed intervals. But this is nitpicking on my side of course, your solution elegantly solves the question posted, and the asides are merely notes on corner cases that possibly don't apply to the question anyway. – G. Bach Mar 10 '13 at 01:15
  • How do I find the %age overlap between these two ranges? `(a, b), (c, d) = [10,17], [16, 20]` should give me a percentage overlap of 2/5 = 40% – DJ_Stuffy_K Mar 06 '18 at 20:04
3

Use zip to group the starting and ending points together. Then use max to find the largest starting point, and min to find the smallest end point:

>>> def compute_overlap(pairs):
...     starts, ends = zip(*pairs)
...     return max(starts), min(ends)
... 
>>> compute_overlap(([10, 20], [15,20]))
(15, 20)
glyphobet
  • 1,564
  • 11
  • 17
1

Assuming you have an iterable and you want to compute to overlap of adjacent items ...

You need to yield the elements "pairwise". Usually, this is as easy as:

seq = [[10, 20], [15, 20]]
for lower,upper in zip(seq,seq[1:]):
    if upper[0] > lower[1]:
        print lower[1],upper[0] 
    else:
        print None, None

Unfortunately, the slicing only works properly with sequences, not arbitrary iterables. It's not hard to generalize though:

def funny_zip(seq):
    iseq = iter(seq)
    current = next(iseq):
    for item in iseq:
        yield current,item
        current = item

Now you can just use:

for lower,upper in funny_zip(seq):
    ...
mgilson
  • 300,191
  • 65
  • 633
  • 696