Какой самый эффективный способ проверить два целочисленных диапазона на совпадение?

Question

Учитывая два включенных целочисленных диапазона [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);
}

Но я ожидаю, что есть более эффективные способы вычисления этого.

Какой метод будет наиболее эффективным с точки зрения наименьшего количества операций.

Answer 1

Что означает перекрытие диапазонов? Это означает, что существует некоторое число C, которое находится в обоих диапазонах, т.е.

x1 <= C <= x2

и

y1 <= C <= y2

Теперь, если мы допустим, что диапазоны правильно сформированы (так что x1

x1 <= y2 && y1 <= x2

Answer 2

Учитывая два диапазона [x1, x2], [y1, y2]

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

Answer 3

Это может легко исказить нормальный человеческий мозг, поэтому я обнаружил, что визуальный подход легче понять:

le Объяснение

Еслидва диапазона "слишком толстые" , чтобы поместиться в слот, который в точности равен сумме ширины обоих, тогда они перекрываются.

Для диапазонов [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!
}

Answer 4

Отличный ответ от Саймон , но мне было проще подумать об обратном случае.

Когда 2 диапазона не перекрываются? Они не перекрываются, когда один из них начинается после того, как другой заканчивается:

dont_overlap = x2 < y1 || x1 > y2

Теперь легко выразить, когда они перекрываются:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

Answer 5

Вычитание минимума из концов диапазонов из максимума начала, кажется, делает свое дело. Если результат меньше или равен нулю, мы имеем перекрытие. Это хорошо визуализирует:

Answer 6

Полагаю, вопрос был о самом быстром, а не самом коротком коде. Самая быстрая версия должна избегать веток, поэтому мы можем написать что-то вроде этого:

для простого случая:

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

Answer 7

return x2 >= y1 && x1 <= y2;

Answer 8

Если вы имели дело с заданными двумя диапазонами [x1:x2] и [y1:y2], то естественный / анти-естественный порядок варьируется одновременно, где:

• естественный порядок: x1 <= x2 && y1 <= y2 или
• антиприродный заказ: x1 >= x2 && y1 >= y2

тогда вы можете использовать это для проверки:

они перекрываются <=> (y2 - x1) * (x2 - y1) >= 0

, где задействованы только четыре операции:

• два вычитания
• одно умножение
• одно сравнение

Answer 9

Мой случай другой. Я хочу проверить два временных диапазона перекрытия. не должно быть частичного совпадения времени. Вот реализация Go.

    func CheckRange(as, ae, bs, be int) bool {
    return (as >= be) != (ae > bs)
    }

Контрольные примеры

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")
    }

Вы можете видеть, что в сравнении границ есть шаблон XOR

Answer 10

Подумайте в обратном порядке : как сделать так, чтобы 2 диапазона не перекрывались ?Если задано [x1, x2], то [y1, y2] должно быть вне [x1, x2], т. Е. y1 < y2 < x1 or x2 < y1 < y2, что эквивалентно y2 < x1 or x2 < y1.

Следовательно, условие сделать 2 диапазонаперекрытие: not(y2 < x1 or x2 < y1), что эквивалентно y2 >= x1 and x2 >= y1 (то же самое с принятым ответом Саймоном).