Der einfachste Weg, um den Schnittpunkt zweier Intervalle zu finden

Im Moment blieb ich bei einem Problem. Es scheint wirklich trivial zu sein, aber es fällt mir immer noch schwer, eine geeignete Lösung zu finden. Das Problem ist: Man hat zwei Intervalle und soll deren Schnittpunkt finden.

Zum Beispiel:

• Schnittpunkt von [0, 3] & [2, 4] ist [2, 3]
• Der Schnittpunkt von [-1, 34] & [0, 4] ist [0, 4]
• Der Schnittpunkt von [0, 3] und [4, 4] ist leer

Es ist ziemlich klar, dass das Problem durch Tests aller möglichen Fälle gelöst werden kann, aber es wird viel Zeit in Anspruch nehmen und ist sehr fehleranfällig. Gibt es eine einfachere Möglichkeit, das Problem anzugehen? Wenn Sie wissen, dass die Lösung mir hilft, bitte. Wird sehr dankbar sein.

Wir können eine Lösung für dieses Problem folgendermaßen definieren. Angenommen, die Eingabeintervalle können definiert werden als und I b = [ b s , b e ] , während das Ausgabeintervall als I o = [ o s , o e ] definiert ist . Wir können den Schnittpunkt I o = I a ⋂ I b finden, indem wir Folgendes tun:$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 ( oder a s > b e ) { return ∅ }$b_s \gt a_e$$a_s \gt b_e$ $\emptyset$

sonst {

$o_s = \max (a_s,b_s)$

$o_e = \min (a_e,b_e)$

return $[o_s,o_e]$

}}

Angenommen, wir haben nur zwei Eingabeintervalle.

1. Stellen Sie sicher, dass die Startzeit des ersten Intervalls <die Startzeit des zweiten Intervalls ist.
2. Überlappung bedeutet, dass die Endzeit eines Intervalls nach der Startzeit eines anderen Intervalls liegt

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

• Zeitliche Komplexität: O (1)
• Raumkomplexität: O (1)

Auf eine andere einfache Weise

Gegeben:
2 Intervalle
Intervall 1 : (Start1, Ende1)
Intervall 2 : (Start2, Ende2)

Erforderlich:
Boolesche Bedingung, um zu überprüfen, ob beide Intervalle geschnitten sind oder nicht

Lösung: Die
folgenden ZWEI Bedingungen sollten zutreffen, um zu berücksichtigen, dass zwei Intervalle geschnitten werden:
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
    // ...

}