What s the most efficient way to test two integer ranges for overlap

Question

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  gt   y1  amp  amp  x1  lt   y2               x2  gt   y1  amp  amp  x2  lt   y2               y1  gt   x1  amp  amp  y1  lt   x2               y2  gt   x1  amp  amp  y2  lt   x2      But I expect there are more efficient ways to compute this  What method would be the most efficient in terms of fewest operations

User · Answer

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  lt   x2  amp  amp  y1  lt   y2 or  anti-natural order  x1  gt   x2  amp  amp  y1  gt   y2   then you may want to use this to check   they are overlapped  lt     y2 - x1     x2 - y1   gt   0  where only four operations are involved     two subtractions one multiplication one comparison

User · Answer

Given two ranges  x1 x2    y1 y2   def is overlapping x1 x2 y1 y2       return max x1 y1   lt   min x2 y2

User · Answer

Given   x1 x2   y1 y2  then x1  lt   y2    x2  gt   y1 would work always  as       x1     x2 y1      y2  if x1  gt  y2 then they do not overlap or x1     x2     y1     y2  if x2  lt  y1 they do not overlap

User · Answer

return x2  gt   y1  amp  amp  x1  lt   y2

User · Answer

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  gt   be      ae  gt  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

User · Answer

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  lt  y1    x1  gt  y2   Now it easy to express when they do overlap   overlap    dont overlap     x2  lt  y1    x1  gt  y2     x2  gt   y1  amp  amp  x1  lt   y2

User · Answer

This can easily warp a normal human brain  so I ve found a visual approach to be easier to understand     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  lt  w1   w2          if max a2  b2  - min a1  b1   lt   a2 - a1     b2 - b1         too fat -- they overlap

User · Answer

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  lt  y2  amp  amp  y1  lt  x2     return  bool    unsigned int   y1-x2  amp  x1-y2     gt  gt   sizeof int  8-1         or  for this case   static inline bool check ov2 int x1  int x2  int y1  int y2          insetead of x1  lt   y2  amp  amp  y1  lt   x2     return  bool     unsigned int   x2-y1   y2-x1     gt  gt   sizeof int  8-1   1

User · Answer

If someone is looking for a one-liner which calculates the actual overlap   int overlap     x2  gt  y1    y2  lt  x1     0    y2  gt   y1  amp  amp  x2  lt   y1   y1   y2  -   x2  lt   x1  amp  amp  y2  gt   x1   x1   x2    1    max 11 operations   If you want a couple fewer operations  but a couple more variables   bool b1   x2  lt   y1  bool b2   y2  gt   x1  int overlap      b1     b2     0    y2  gt   y1  amp  amp  b1   y1   y2  -   x2  lt   x1  amp  amp  b2   x1   x2    1     max 9 operations

User · Answer

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  lt  xmax    i      if  ymin  lt   i  amp  amp  i  lt   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

User · Answer

You have the most efficient representation already - it s the bare minimum that needs to be checked unless you know for sure that x1  lt  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

User · Answer

What does it mean for the ranges to overlap  It means there exists some number C which is in both ranges  i e  x1  lt   C  lt   x2  and y1  lt   C  lt   y2  Now  if we are allowed to assume that the ranges are well-formed  so that x1  lt   x2 and y1  lt   y2  then it is sufficient to test x1  lt   y2  amp  amp  y1  lt   x2

User · Answer

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

User · Answer

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  lt  y2  lt  x1 or x2  lt  y1  lt  y2 which is equivalent to y2  lt  x1 or x2  lt  y1   Therefore  the condition to make the 2 ranges overlap  not y2  lt  x1 or x2  lt  y1   which is equivalent to y2  gt   x1 and x2  gt   y1  same with the accepted answer by Simon

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

Examples related to performance

Examples related to comparison

Examples related to integer

Examples related to range