¿Cuál es la forma más eficaz de comprobar si dos rangos se superponen?
Dados dos rangos inclusivos [x1:x2] y [y1:y2], donde x1 ≤ x2y y1 ≤ y2, ¿cuál es la forma más eficiente de probar si existe alguna superposición de los dos rangos?
Una implementación simple es la siguiente:
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);
}
Pero espero que haya formas más eficientes de calcular esto.
¿Qué método sería el más eficiente en términos de menor número de operaciones?
¿Qué significa que los rangos se superpongan? Significa que existe algún número C que está en ambos rangos, es decir
x1 <= C <= x2
y
y1 <= C <= y2
Para evitar confusiones, considerando los rangos son: [x1:x2] y [y1:y2]
Ahora, si se nos permite suponer que los rangos están bien formados (de modo que x1 <= x2 e y1 <= y2), entonces es suficiente probar
x1 <= y2 && y1 <= x2
O
(InicioA <= FinB) y (FinA >= InicioB)
Dados dos rangos [x1,x2], [y1,y2]
def is_overlapping(x1,x2,y1,y2):
return max(x1,y1) <= min(x2,y2)
Esto puede deformar fácilmente un cerebro humano normal, por lo que encontré que un enfoque visual es más fácil de entender:
la explicación
Si dos rangos son "demasiado anchos" para caber en una ranura que es exactamente la suma del ancho de ambos, entonces se superponen.
Para rangos [a1, a2]y [b1, b2]esto sería:
/**
* 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!
}
Gran respuesta de Simon , pero para mí fue más fácil pensar en caso contrario.
¿Cuándo no se superponen 2 rangos? No se superponen cuando uno de ellos comienza después de que termina el otro:
dont_overlap = x2 < y1 || x1 > y2
Ahora es fácil expresar cuándo se superponen:
overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
