Для двух инклюзивных целых диапазонов [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
Учитывая два диапазона [x1, x2], [y1, y2]
def is_overlapping(x1,x2,y1,y2):
return max(x1,y1) <= min(x2,y2)
Это может легко деформировать нормальный человеческий мозг, поэтому я нашел визуальный подход более понятным:
Если два диапазона "слишком толстые", чтобы соответствовать слоту, который является точно суммой ширины обоих, то они перекрываются.
Для диапазонов [a1, a2] и [b1, b2] это будет:
/**
* 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!
}
Отличный ответ от Simon, но для меня было легче подумать об обратном случае.
Когда 2 диапазона не перекрываются? Они не перекрываются, когда один из них запускается после того, как заканчивается другой:
dont_overlap = x2 < y1 || x1 > y2
Теперь легко выразить, когда они перекрываются:
overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
Вычитание минимума концов диапазонов от максимума начала, похоже, делает трюк. Если результат меньше или равен нулю, мы имеем перекрытие. Это хорошо его визуализирует:
Я предполагаю, что речь шла о самом быстром, а не кратчайшем. Самая быстрая версия должна избегать ветвей, поэтому мы можем написать что-то вроде этого:
для простого случая:
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));
};
или, для этого случая:
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);
};
return x2 >= y1 && x1 <= y2;
Если вы имели дело с двумя диапазонами [x1:x2] и [y1:y2], естественный/антиестественный порядок изменяется в то же время, когда:
x1 <= x2 && y1 <= y2 илиx1 >= x2 && y1 >= y2то вы можете использовать это для проверки:
они перекрываются <= > (y2 - x1) * (x2 - y1) >= 0
где задействуются только четыре:
У вас есть наиболее эффективное представление уже - это минимальный минимум, который нужно проверить, если вы точно не знаете, что x1 < x2 и т.д., затем используйте другие решения, предоставленные другими пользователями.
Вероятно, вы должны заметить, что некоторые компиляторы действительно оптимизируют это для вас - возвращаясь, как только любое из этих выражений вернет true. Если кто-то возвращает true, то и конечный результат - так что другие проверки можно просто пропустить.
Если кто-то ищет однострочный калькулятор, который вычисляет фактическое перекрытие:
int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations
Если вы хотите еще пару операций, но еще пару переменных:
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
Подумайте наоборот: как сделать так, чтобы 2 диапазона не перекрывались? Учитывая [x1, x2], тогда [y1, y2] должно быть за пределами [x1, x2], т. y1 < y2 < x1 or x2 < y1 < y2 что эквивалентно y2 < x1 or x2 < y1.
Следовательно, условие перекрытия двух диапазонов: not(y2 < x1 or x2 < y1), что эквивалентно y2 >= x1 and x2 >= y1 (то же самое, что и принятый ответ Саймона).
Здесь моя версия:
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;
Если вы не используете высокопроизводительную проверку диапазона на миллиардах широкоразмерных целых чисел, наши версии должны работать аналогичным образом. Я хочу сказать, что это микро-оптимизация.