31

is there a built in function to compute the overlap between two discrete intervals, e.g. the overlap between [10, 15] and [20, 38]? In that case the overlap is 0. If it's [10, 20], [15, 20], the overlap is 5.

Ciro Santilli Путлер Капут 六四事
  • 302,449
  • 85
  • 1,093
  • 879
  • Do you mean that if you want the overlap between [10,25] and [20,38], that the result should be [20,25]? – Marc Jun 01 '10 at 23:06
  • What do you mean overlap? Please give an example of the expected result. – Chinmay Kanchi Jun 01 '10 at 23:06
  • 3
    there is overlap between [10,15] and [20,38]? – joaquin Jun 01 '10 at 23:07
  • why is the overlap of [10, 20] and [15, 20] 5 and not 6? there are 6 values that overlap in those two intervals (15, 16, 17, 18, 19, and 20). if they are exclusive intervals rather than inclusive, then there are 4 overlapping values (16, 17, 18, and 19). – Dave Cousineau Mar 27 '15 at 22:46
  • @Marc if one wants [20,25] what is the best way to do it? please point me to any similar questions. I'm trying to achieve exactly this ^ – DJ_Stuffy_K Mar 06 '18 at 18:21

5 Answers5

81

You can use max and min:

>>> def getOverlap(a, b):
...     return max(0, min(a[1], b[1]) - max(a[0], b[0]))

>>> getOverlap([10, 25], [20, 38])
5
>>> getOverlap([10, 15], [20, 38])
0
Mark Byers
  • 767,688
  • 176
  • 1,542
  • 1,434
  • 1
    unless the intervals are implied to be exclusive on the first value and inclusive on the second (or something like that...), this would need a `+ 1` to the subtraction. – Dave Cousineau Mar 27 '15 at 23:06
  • thanks for the answer, how would I go about finding the `percentage overlap` between those ranges? – DJ_Stuffy_K Mar 06 '18 at 19:10
  • @DJ_Stuffy_K for percentage overlap, see mine answer below. Hope it helps. – jhutar Apr 07 '19 at 21:33
15

Check out pyinterval http://code.google.com/p/pyinterval/

import interval
x=interval.interval[10, 15]
y=interval.interval[20, 38]
z=interval.interval[12,18]

print(x & y)
# interval()
print(x & z)
# interval([12.0, 15.0])
unutbu
  • 777,569
  • 165
  • 1,697
  • 1,613
  • 2
    +1 Because I didn't know about that module, though it might be overkill if he just needs it for this one calculation. – Mark Byers Jun 01 '10 at 23:15
  • 1
    The OP was looking for "a built in function". – johnsyweb Jun 02 '10 at 00:47
  • I think although the documentation is the same, the module has changed slightly. The `interval` object does not have any attribute named `interval`anymore... – T-800 Aug 01 '14 at 13:41
  • @T-1000: When you `import interval`, `interval` refers to the module. `interval.interval` refers to the `interval` class. In contrast, when you use `from interval import interval`, then `interval` refers to the class. In neither case is there any reference to an `interval` attribute. – unutbu Aug 01 '14 at 14:11
  • @unutbu Thanks for your explanation. I think there is very similar module called `interval`. I have installed using `pip install interval` and the codes you provided did not function. Then I tried to install `pip install pyinterval` but, I got "Could not find a version that satisfies the requirement pyinterval (from versions: 1.0b14, 1.0b21)" error. What can be going wrong? I couldn't find any documentation about requirements... – T-800 Aug 01 '14 at 14:18
  • 1
    @T-1000: Yes, the procedure I used to install it a while back no longer works. Per the instructions [here](https://pypi.python.org/pypi/pyinterval/) you might try `easy_install pyinterval`. Or, I believe you'll need to install [crlibm](http://lipforge.ens-lyon.fr/www/crlibm/download.html), and then download the tar file from the same page and try `python setup.py install`. – unutbu Aug 01 '14 at 14:59
  • Update setuptools and will work with pip install pyinterval – LaintalAy Mar 22 '18 at 15:31
  • It's really fine because it makes possible to check more intervals (not just 2). – szabozoltan Feb 14 '19 at 07:55
2

Here is a good function from Aaron Quinlan's chrom_sweep, modified for your interval representation. It returns the number of bp of overlap if they do overlap, otherwise it returns the distance as a negative int. 

def overlaps(a, b):
    """
    Return the amount of overlap, in bp
    between a and b.
    If >0, the number of bp of overlap
    If 0,  they are book-ended.
    If <0, the distance in bp between them
    """

    return min(a[1], b[1]) - max(a[0], b[0])
The Unfun Cat
  • 26,783
  • 25
  • 102
  • 145
2

Just wrote this:

def overlap(interval1, interval2):
    """
    Given [0, 4] and [1, 10] returns [1, 4]
    """
    if interval2[0] <= interval1[0] <= interval2[1]:
        start = interval1[0]
    elif interval1[0] <= interval2[0] <= interval1[1]:
        start = interval2[0]
    else:
        raise Exception("Intervals are not overlapping")

    if interval2[0] <= interval1[1] <= interval2[1]:
        end = interval1[1]
    elif interval1[0] <= interval2[1] <= interval1[1]:
        end = interval2[1]
    else:
        raise Exception("Intervals are not overlapping")

    return (start, end)


def percentage_overlap(interval1, interval2):
    """
    Given [0, 4] and [1, 10] returns 0.75
    """
    try:
        overlap = _overlap(interval1, interval2)
    except Exception:
        return 0.0
    return (overlap[1] - overlap[0]) / (interval1[1] - interval1[0])
jhutar
  • 1,262
  • 2
  • 17
  • 31
1

I had to process inclusive bounds so the current answers did not work. Here is a solution with inclusive bounds if you only care about a True/False answer:

def overlap(first: int, last: int, another_first: int, another_last: int)->bool:
    """
    Return True if the two intervals overlap.

    >>> not any([
    ...     _overlap(1, 1, 2, 2),
    ...     _overlap(2, 2, 1, 1)
    ... ])
    True

    >>> all([
    ...     _overlap(1, 1, 1, 1),
    ...     _overlap(1, 5, 1, 1),
    ...     _overlap(1, 1, 1, 5),
    ...     _overlap(1, 3, 2, 5),
    ...     _overlap(2, 5, 1, 3),
    ...     _overlap(1, 5, 2, 3),
    ...     _overlap(2, 3, 1, 5),
    ...  ])
    True
    """
    return min(last, another_last) - max(first, another_first) >= 0
marko.ristin
  • 553
  • 6
  • 6