什么是测试两个整数范围重叠的最有效的方法？ [英] What's the most efficient way to test two integer ranges for overlap?

问题描述

给定两个包含整数范围[x1：x2]和[y1：y2]，其中x1 <= x2和y1 <= y2，测试两个范围是否有任何重叠的最有效的方法是什么？

一个简单的实现如下：

  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）; 
} 
  

但我希望有更有效的方法来计算。

解决方案

什么方法在最少的操作上效率最高？是否意味着范围重叠？这意味着存在在两个范围中的一些数字C，即

  x1 <= C <= x2 
  

和

  y1 <= C <= y2 
  

现在，如果我们允许假设范围（使得x1 <= x2和y1 <= y2），则足以测试

  x1 < = y2&& y1< = x2 
  

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.

解决方案

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

and

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

这篇关于什么是测试两个整数范围重叠的最有效的方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！