Qual é a maneira mais eficiente de testar dois intervalos inteiros para sobreposição?

Dado dois intervalos inteiros inclusivos [x1: x2] e [y1: y2], onde x1 ≤ x2 e y1 ≤ y2, qual é a maneira mais eficiente de testar se existe alguma sobreposição dos dois intervalos?

Uma implementação simples é a seguinte:

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

Mas espero que haja maneiras mais eficientes de calcular isso.

Qual método seria o mais eficiente em termos de menos operações.

O que significa que os intervalos se sobrepõem? Isso significa que existe algum número C que está em ambos os intervalos, ou seja,

x1 <= C <= x2

e

y1 <= C <= y2

Agora, se pudermos assumir que os intervalos estão bem formados (de modo que x1 <= x2 e y1 <= y2), então é suficiente testar

x1 <= y2 && y1 <= x2

Dado dois intervalos [x1, x2], [y1, y2]

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

Isso pode deformar facilmente um cérebro humano normal, então achei uma abordagem visual mais fácil de entender:

le Explicação

Se dois intervalos são "muito gordos" para caber em um slot que é exatamente a soma da largura de ambos, eles se sobrepõem.

Para intervalos [a1, a2]e [b1, b2]isso seria:

/**
 * 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!
}

Ótima resposta de Simon , mas para mim foi mais fácil pensar em caso inverso.

Quando 2 faixas não se sobrepõem? Eles não se sobrepõem quando um deles começa depois que o outro termina:

dont_overlap = x2 < y1 || x1 > y2

Agora é fácil expressar quando eles se sobrepõem:

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

Subtrair o mínimo dos fins dos intervalos do máximo do início parece ser suficiente. Se o resultado for menor ou igual a zero, temos uma sobreposição. Isso visualiza bem:

Suponho que a pergunta era sobre o código mais rápido, não o mais curto. A versão mais rápida precisa evitar ramificações, para que possamos escrever algo como isto:

para casos simples:

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

ou, para este caso:

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;

Se você estava lidando com, dado dois intervalos [x1:x2]e [y1:y2], ordem natural / antinatural varia ao mesmo tempo em que:

• ordem natural: x1 <= x2 && y1 <= y2ou
• ordem anti-natural: x1 >= x2 && y1 >= y2

você pode usar isso para verificar:

eles estão sobrepostos <=> (y2 - x1) * (x2 - y1) >= 0

onde apenas quatro operações estão envolvidas:

• duas subtrações
• uma multiplicação
• uma comparação

Se alguém estiver procurando por uma linha que calcule a sobreposição real:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

Se você deseja menos operações, mas mais algumas variáveis:

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

Pense de maneira inversa : como fazer as duas faixas não se sobreporem ? Dado [x1, x2], então [y1, y2]deve estar fora [x1, x2] , ou seja, o y1 < y2 < x1 or x2 < y1 < y2que equivale ay2 < x1 or x2 < y1 .

Portanto, a condição para fazer os 2 intervalos se sobrepõe:, o not(y2 < x1 or x2 < y1)que é equivalente a y2 >= x1 and x2 >= y1(o mesmo com a resposta aceita por Simon).

Você já tem a representação mais eficiente - é o mínimo necessário que deve ser verificado, a menos que você tenha certeza de que x1 <x2 etc, e use as soluções fornecidas por outras pessoas.

Você provavelmente deve observar que alguns compiladores realmente otimizarão isso para você - retornando assim que qualquer uma dessas 4 expressões retornar verdadeira. Se um retornar verdadeiro, o resultado final será o mesmo - para que as outras verificações possam ser ignoradas.

Meu caso é diferente. Eu quero verificar dois intervalos de tempo se sobrepõem. não deve haver sobreposição de tempo unitário. aqui está a implementação Go.

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

Casos de teste

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

você pode ver que existe um padrão XOR na comparação de limites

Aqui está a minha versão:

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;

A menos que você esteja executando um verificador de intervalo de alto desempenho em bilhões de números inteiros com espaçamento amplo, nossas versões deverão ter o mesmo desempenho. O que quero dizer é que isso é micro-otimização.