A maneira mais fácil de encontrar a interseção de dois intervalos

Agora eu fiquei com um problema. Parece ser realmente trivial, mas ainda assim é difícil encontrar uma solução apropriada. O problema é: um tem dois intervalos e deve encontrar a interseção deles.

Por exemplo:

• A interseção de [0, 3] e [2, 4] é [2, 3]
• A interseção de [-1, 34] e [0, 4] é [0, 4]
• A interseção de [0, 3] e [4, 4] está vazia

É bastante claro que o problema pode ser resolvido usando testes de todos os casos possíveis, mas isso levará muito tempo e é muito propenso a erros. Existe alguma maneira mais fácil de resolver o problema? Se você souber que a solução me ajuda, por favor. Ficarei muito grato.

Podemos definir uma solução para esse problema da seguinte maneira. Consideram-se os intervalos de entrada pode ser definido como e I b = $I_{a} = [a_s, a_e]$ , enquanto o intervalo de saída é definido como I o = [ o s , o e ] . Podemos encontrar a interseção I o = I a ⋂ I b fazendo o seguinte:$I_{b} = [b_s, b_e]$$I_{o} = [o_s, o_e]$$I_{o} = I_{a} \bigcap I_{b}$

se ( ou a s > b e ) { retornar ∅ }$b_s \gt a_e$$a_s \gt b_e$ $\emptyset$

mais {

$o_s = \max (a_s,b_s)$

$o_e = \min (a_e,b_e)$

retornar $[o_s,o_e]$

}

Suponha que temos apenas dois intervalos de entrada.

1. Verifique se a hora de início do primeiro intervalo <a hora de início do segundo intervalo.
2. Sobreposição significa que a hora de término de um intervalo é posterior à hora de início de outro 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;
    }
}

• Complexidade temporal: O (1)
• Complexidade do espaço: O (1)

De outra maneira simples

Dado:
2 intervalos
Intervalo 1 : (início1, fim1)
Intervalo 2 : (início2, fim2)

Necessário:
Condição booleana para verificar se os dois intervalos estão cruzados ou não

Solução: As
seguintes DUAS condições devem ser verdadeiras para considerar que dois intervalos são cruzados:
1. fim2> = início1
2. início2 <= fim1

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

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

}