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

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

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

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.

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);
};
```

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

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.