La forma más fácil de encontrar la intersección de dos intervalos.

En este momento me quedé con un problema. Parece ser realmente trivial, pero aún así es difícil para mí encontrar una solución adecuada. El problema es: uno tiene dos intervalos y debe encontrar la intersección de ellos.

Por ejemplo:

• La intersección de [0, 3] y [2, 4] es [2, 3]
• La intersección de [-1, 34] y [0, 4] es [0, 4]
• La intersección de [0, 3] y [4, 4] es un conjunto vacío

Está bastante claro que el problema se puede resolver mediante el uso de pruebas de todos los casos posibles, pero llevará mucho tiempo y es muy propenso a errores. ¿Hay alguna manera más fácil de abordar el problema? Si conoces la solución, ayúdame, por favor. Estaré muy agradecido.

Podemos definir una solución a este problema de la siguiente manera. Suponga que los intervalos de entrada se pueden definir como e , mientras que el intervalo de salida se define como . Podemos encontrar la intersección haciendo lo siguiente:I b = [ b s , b e ] I o = [ o s , o e ] I o = I a ⋂ I $I_{a} = [a_s, a_e]$$I_{b} = [b_s, b_e]$$I_{o} = [o_s, o_e]$$I_{o} = I_{a} \bigcap I_{b}$

if ( o ) { return }a s > b e$b_s \gt a_e$$a_s \gt b_e$ $\emptyset$

más {

$o_s = \max (a_s,b_s)$

$o_e = \min (a_e,b_e)$

volver $[o_s,o_e]$

}

Supongamos que solo tenemos dos intervalos de entrada.

1. Asegúrese de que la hora de inicio del primer intervalo <la hora de inicio del segundo intervalo.
2. La superposición significa que la hora de finalización de un intervalo es posterior a la hora de inicio de otro intervalo

public int[] overlap(int[] i1, int[] i2) {
    // Make sure the start time of first interval < the start time of second interval.
    if(i1.startTime > i2.startTime) {
        return overlap(i2, i1);
    }

    // Overlap means an interval's end time is after another interval's start time
    if(i1.endTime > i2.startTime) {
        return new Interval(i2.startTime, Math.min(i1.endTime, i2.endTime));
    }
    else {
        return null;
    }
}

• Complejidad del tiempo: O (1)
• Complejidad espacial: O (1)

De otra manera simple

Dado:
2 Intervalos
Intervalo 1 : (inicio1, final1)
Intervalo 2 : (inicio2, final2)

Requerido:
condición booleana para verificar si ambos intervalos están intersectados o no

Solución: Las
siguientes DOS condiciones deben ser ciertas para considerar que 2 intervalos están intersectados:
1. end2> = start1
2. start2 <= end1

// check 2 intervals are intersected or not
if( (end2 >= start1) && (start2 <= end1) ){
    // 2 intervals are intersected
    // ...

}else{
    // 2 intervals are NOT intersected
    // ...

}