[performance] What's the most efficient way to test two integer ranges for overlap?

Given two inclusive integer ranges [x1:x2] and [y1:y2], where x1 = x2 and y1 = y2, what is the most efficient way to test whether there is any overlap of the two ranges?

A simple implementation is as follows:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

But I expect there are more efficient ways to compute this.

What method would be the most efficient in terms of fewest operations.

This question is related to performance comparison integer range

The answer is


If someone is looking for a one-liner which calculates the actual overlap:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

If you want a couple fewer operations, but a couple more variables:

bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; // max 9 operations

Think in the inverse way: how to make the 2 ranges not overlap? Given [x1, x2], then [y1, y2] should be outside [x1, x2], i.e., y1 < y2 < x1 or x2 < y1 < y2 which is equivalent to y2 < x1 or x2 < y1.

Therefore, the condition to make the 2 ranges overlap: not(y2 < x1 or x2 < y1), which is equivalent to y2 >= x1 and x2 >= y1 (same with the accepted answer by Simon).


You have the most efficient representation already - it's the bare minimum that needs to be checked unless you know for sure that x1 < x2 etc, then use the solutions others have provided.

You should probably note that some compilers will actually optimise this for you - by returning as soon as any of those 4 expressions return true. If one returns true, so will the end result - so the other checks can just be skipped.


Given: [x1,x2] [y1,y2] then x1 <= y2 || x2 >= y1 would work always. as

      x1 ... x2
y1 .... y2

if x1 > y2 then they do not overlap or

x1 ... x2
    y1 ... y2

if x2 < y1 they do not overlap.


I suppose the question was about the fastest, not the shortest code. The fastest version have to avoid branches, so we can write something like this:

for simple case:

static inline bool check_ov1(int x1, int x2, int y1, int y2){
    // insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};

or, for this case:

static inline bool check_ov2(int x1, int x2, int y1, int y2){
    // insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};

Great answer from Simon, but for me it was easier to think about reverse case.

When do 2 ranges not overlap? They don't overlap when one of them starts after the other one ends:

dont_overlap = x2 < y1 || x1 > y2

Now it easy to express when they do overlap:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

Here's my version:

int xmin = min(x1,x2)
  , xmax = max(x1,x2)
  , ymin = min(y1,y2)
  , ymax = max(y1,y2);

for (int i = xmin; i < xmax; ++i)
    if (ymin <= i && i <= ymax)
        return true;

return false;

Unless you're running some high-performance range-checker on billions of widely-spaced integers, our versions should perform similarly. My point is, this is micro-optimization.


return x2 >= y1 && x1 <= y2;

If you were dealing with, given two ranges [x1:x2] and [y1:y2], natural / anti-natural order ranges at the same time where:

  • natural order: x1 <= x2 && y1 <= y2 or
  • anti-natural order: x1 >= x2 && y1 >= y2

then you may want to use this to check:

they are overlapped <=> (y2 - x1) * (x2 - y1) >= 0

where only four operations are involved:

  • two subtractions
  • one multiplication
  • one comparison

Given two ranges [x1,x2], [y1,y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

This can easily warp a normal human brain, so I've found a visual approach to be easier to understand:

overlap madness

le Explanation

If two ranges are "too fat" to fit in a slot that is exactly the sum of the width of both, then they overlap.

For ranges [a1, a2] and [b1, b2] this would be:

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  // too fat -- they overlap!
}

My case is different. i want check two time ranges overlap. there should not be a unit time overlap. here is Go implementation.

    func CheckRange(as, ae, bs, be int) bool {
    return (as >= be) != (ae > bs)
    }

Test cases

if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 6, 9) != true {
        t.Error("Expected 2,8,6,9 to equal TRUE")
    }

    if CheckRange(2, 8, 8, 9) != false {
        t.Error("Expected 2,8,8,9 to equal FALSE")
    }

    if CheckRange(2, 8, 4, 6) != true {
        t.Error("Expected 2,8,4,6 to equal TRUE")
    }

    if CheckRange(2, 8, 1, 9) != true {
        t.Error("Expected 2,8,1,9 to equal TRUE")
    }

    if CheckRange(4, 8, 1, 3) != false {
        t.Error("Expected 4,8,1,3 to equal FALSE")
    }

    if CheckRange(4, 8, 1, 4) != false {
        t.Error("Expected 4,8,1,4 to equal FALSE")
    }

    if CheckRange(2, 5, 6, 9) != false {
        t.Error("Expected 2,5,6,9 to equal FALSE")
    }

    if CheckRange(2, 5, 5, 9) != false {
        t.Error("Expected 2,5,5,9 to equal FALSE")
    }

you can see there is XOR pattern in boundary comparison


Subtracting the Minimum of the ends of the ranges from the Maximum of the beginning seems to do the trick. If the result is less than or equal to zero, we have an overlap. This visualizes it well:

enter image description here


Examples related to performance

Why is 2 * (i * i) faster than 2 * i * i in Java? What is the difference between spark.sql.shuffle.partitions and spark.default.parallelism? How to check if a key exists in Json Object and get its value Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly? Most efficient way to map function over numpy array The most efficient way to remove first N elements in a list? Fastest way to get the first n elements of a List into an Array Why is "1000000000000000 in range(1000000000000001)" so fast in Python 3? pandas loc vs. iloc vs. at vs. iat? Android Recyclerview vs ListView with Viewholder

Examples related to comparison

Wildcard string comparison in Javascript How to compare two JSON objects with the same elements in a different order equal? Comparing strings, c++ Char Comparison in C bash string compare to multiple correct values Comparing two hashmaps for equal values and same key sets? Comparing boxed Long values 127 and 128 Compare two files report difference in python How do I fix this "TypeError: 'str' object is not callable" error? Compare cell contents against string in Excel

Examples related to integer

Python: create dictionary using dict() with integer keys? How to convert datetime to integer in python Can someone explain how to append an element to an array in C programming? How to get the Power of some Integer in Swift language? python "TypeError: 'numpy.float64' object cannot be interpreted as an integer" What's the difference between integer class and numeric class in R PostgreSQL: ERROR: operator does not exist: integer = character varying C++ - how to find the length of an integer Converting binary to decimal integer output Convert floats to ints in Pandas?

Examples related to range

How does String substring work in Swift Creating an Array from a Range in VBA How to create range in Swift? Why is "1000000000000000 in range(1000000000000001)" so fast in Python 3? How to find integer array size in java How does one make random number between range for arc4random_uniform()? Skip over a value in the range function in python Excel Define a range based on a cell value How can I generate a random number in a certain range? Subscript out of range error in this Excel VBA script