Take the 2-minute tour ×

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.

share|improve this question
add comment

7 Answers

up vote 32 down vote accepted

What does it mean for the ranges to overlap? It means there exists some number C which is in both ranges, i.e.

x1 <= C <= x2


y1 <= C <= y2

Now, if we are allowed to assume that the ranges are well-formed (so that x1 <= x2 and y1 <= y2) then it is sufficient to test

x1 <= y2 && y1 <= x2
share|improve this answer
I believe it should be x1 <= y2 && y1 >= x2, no? –  David Beck Mar 27 '13 at 22:40
@DavidBeck: no, if y1 > x2 then the ranges definitely don't overlap (e.g. consider [1:2] and [3:4]: y1 = 3 and x2 = 2, so y1 > x2, but there's no overlap). –  Simon Nickerson Mar 28 '13 at 9:14
add comment

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

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)
share|improve this answer
add comment

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);
share|improve this answer
add comment
return x2 >= y1 && x1 <= y2;
share|improve this answer
This assumes y1 < y2 and x1 < x2, which isn't specified. –  Mark H Jul 16 '10 at 23:16
I've added that assumption. –  WilliamKF Jul 16 '10 at 23:41
In that case, this solution is sufficient. –  Mark H Jul 16 '10 at 23:45
add comment

x1 < y1 ? return y1 < x2 : return x2 > y1;

share|improve this answer
Gives wrong answer for [x1:x2]=[3:4], [y1:y2]=[1:2]. Also, it is suspicious that your answer does not reference y2. –  Simon Nickerson Jul 18 '10 at 17:48
add comment

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.

share|improve this answer
All compilers will. All (to my knowledge) currently-used languages with C-style syntax (C, C++, C#, Java, etc.) employ short-circuited boolean operators and it is part of the various standards that govern those languages. If the result of the lefthand value is sufficient to determine the result of the operation, the righthand value is not evaluated. –  Jonathan Grynspan Jul 16 '10 at 23:46
Mark H -- the compiler will skip over the second clause if it can: so if you have a function that says: foo(int c) { int i=0; if (c < 3 || ++i == argc) printf("Inside\n"); printf("i is %d\n", i); Foo(2) will print: Inside i is 0 and Foo(4) will print: i is 1 (tested on gcc 4.4.3, but I've relied on this behavior for some ugly code in icc as well) –  J Teller Jul 17 '10 at 0:02
add comment

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.

share|improve this answer
I think you've gone over the specification here. It's assumed that x1 to x2 is ascending/decending (either way, it's sorted) - there's no need for a loop, you only need to check the head and tail elements. I do prefer the min/max solution though - simply because it's easier to read when you come back to the code later. –  Mark H Jul 16 '10 at 23:42
-1: this is not micro-optimisation; this is choosing an appropriate algorithm. Your algorithm is O(n) when there is a simple O(1) choice. –  Simon Nickerson Jul 18 '10 at 17:51
add comment

Your Answer


