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

8

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.

ohidano
fuente
¿Qué hay de malo en mi pregunta? ¿Por qué fue rechazado?
ohidano
2
Un par de cosas ... esta parece ser una pregunta de tarea, si es así, debe llamarla y etiquetarla como tal. El contexto de su problema tampoco está claro. Podría interpretarse como un problema puramente matemático (en cuyo caso pertenece a Math.SE, no aquí), o un ejercicio de programación.
Spencer Bryngelson
En caso de que esté buscando un nombre para estos métodos, se llama Interval Arithmetic .
André

Respuestas:

17

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 aI bIa=[as,ae]Ib=[bs,be]Io=[os,oe]Io=IaIb

if ( o ) { return }a s > b ebs>aeas>be

más {

os=max(as,bs)

oe=min(ae,be)

volver [os,oe]

}

spektr
fuente
1

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)
motorix
fuente
0

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
    // ...

}
ahmednabil88
fuente