Mögliche Interviewfrage: So finden Sie alle überlappenden Intervalle

Es ist nicht eine Interviewfrage per se , als ich auf das in meinem Projekt kam, aber ich dachte , es könnte eine anständige intervew Frage sein.

Sie haben N Intervallpaare, sagen wir ganze Zahlen. Sie müssen alle Intervalle identifizieren, die sich in O (N) -Zeit überschneiden. Zum Beispiel, wenn Sie haben

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

Die Antwort lautet {1, 3}, {12, 14}, {2, 4}, {13, 15}. Beachten Sie, dass Sie sie nicht gruppieren müssen, damit das Ergebnis in beliebiger Reihenfolge wie im Beispiel angezeigt werden kann.

Ich habe gerade O (N) -Zeit eingegeben, weil der KMP-Algorithmus O (N) für die Zeichenfolgensuche verwendet. : D.

Das Beste, was ich mir ausgedacht habe und was ich gerade im Projekt verwende, ist O (N ^ 2). Ja, Brute Force ist ziemlich traurig, aber niemand beschwert sich, also werde ich es nicht umgestalten. : P Trotzdem war ich neugierig, ob ein größerer Geist eine elegantere Lösung hat.

Werfen Sie die Endpunkte der Intervalle in ein Array und markieren Sie sie entweder als Start- oder Endpunkte. Sortieren Sie sie, indem Sie die Bindungen lösen, indem Sie Endpunkte vor Startpunkten platzieren, wenn die Intervalle geschlossen sind, oder umgekehrt, wenn sie halb geöffnet sind.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E

Durchlaufen Sie dann die Liste und verfolgen Sie, in wie vielen Intervallen wir uns befinden (dies entspricht der Anzahl der verarbeiteten Startpunkte abzüglich der Anzahl der Endpunkte). Immer wenn wir einen Startpunkt erreichen, während wir uns bereits in einem Intervall befinden, bedeutet dies, dass wir überlappende Intervalle haben müssen.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
    ^                          ^
   overlap                    overlap

Wir können herausfinden, welche Intervalle sich mit welchen überschneiden, indem wir Daten neben den Endpunkten speichern und verfolgen, in welchen Intervallen wir uns befinden.

Dies ist eine O (N logN) -Lösung, wobei die Sortierung der Hauptfaktor ist.

Sortieren Sie die Intervalle nach Startpunkt. Falten Sie dann diese Liste um und führen Sie jedes Intervall mit seinem Nachbarn (dh (1,4), (2,6) -> (1,6)) zusammen, wenn sie sich überlappen. Die resultierende Liste enthält diese Intervalle ohne überlappenden Partner. Filtern Sie diese aus der ursprünglichen Liste heraus.

Dies ist zeitlich linear nach der anfänglichen Sortieroperation, die mit jedem (n log n) Algorithmus durchgeführt werden kann. Ich bin mir nicht sicher, wie du das umgehen würdest. Selbst die Operation "Duplikate herausfiltern" am Ende ist linear, wenn Sie die bereits sortierte Reihenfolge der Ein- und Ausgabe der ersten Operation nutzen.

Hier ist eine Implementierung in Haskell:

-- Given a list of intervals, select those which overlap with at least one other inteval in the set.
import Data.List

type Interval = (Integer, Integer)

overlap (a1,b1)(a2,b2) | b1 < a2 = False
                       | b2 < a1 = False
                       | otherwise = True

mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2)

sortIntervals::[Interval]->[Interval]
sortIntervals = sortBy (\(a1,b1)(a2,b2)->(compare a1 a2))

sortedDifference::[Interval]->[Interval]->[Interval]
sortedDifference [] _ = []
sortedDifference x [] = x
sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys
                              | x < y  = x:(sortedDifference xs (y:ys))
                              | y < x  = sortedDifference (x:xs) ys

groupIntervals::[Interval]->[Interval]
groupIntervals = foldr couldCombine []
  where couldCombine next [] = [next]
        couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs
                                 | otherwise = next:x:xs

findOverlapped::[Interval]->[Interval]
findOverlapped intervals = sortedDifference sorted (groupIntervals sorted)
  where sorted = sortIntervals intervals

sample = [(1,3),(12,14),(2,4),(13,15),(5,10)]

Der Standardansatz für Online-Probleme besteht darin, sie nach dem Ausgangspunkt zu sortieren und dann einfach vom ersten zum letzten zu gehen. O(n*logn)( O(n)falls bereits sortiert)

end = 0;
for (current in intervals) {
    if current.start < end {
        // there's an intersection!
        // 'current' intersects with some interval before it
        ...
    }
    end = max(end, current.end)
}

Ich bin mir nicht sicher über O (N), aber was ist, wenn wir sie zuerst nach der ersten Zahl in jedem Tupel sortieren und dann nacheinander diejenigen finden, bei denen die erste Zahl des Tupels größer ist als die der größten Zahl, die in früheren Tupeln gesehen wurde, was auch der Fall ist nicht mit dem nächsten Tupel überlappen.

Sie würden also zuerst Folgendes erhalten:

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

da 4 (am größten) <5 und 10 <12 ist, wird {5, 10} isoliert.

Dies würde bedeuten, dass wir die größte Anzahl verfolgen, auf die wir stoßen, und jedes Mal, wenn wir ein Tupel finden, dessen Startnummer größer ist, prüfen wir, ob es sich mit der nächsten überschneidet.

Dies wird dann von der Effizienz des Sortieralgorithmus abhängig, da der letztere Prozess O (N) wäre.

Angenommen, der Unterschied zwischen Start- und Endpunkt ist gering, z. B. <32. Z. 1..32. Dann kann jedes Intervall als Bitmuster in ein 32-Bit-Wort geschrieben werden. zB [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110. Zwei Intervalle oder Kombinationen von Intervallen überlappen sich, wenn ihre bitweise ANDNicht-Null ist. z.B. [1,2]Überlappungen, [1,3]weil 001&011 == 001nicht Null. O (n) alg ist es, ein bitweises ODER der bisher gesehenen Intervalle und ANDjedes neuen Intervalls zu halten :

bitsSoFar = 0
for (n=0; n < bitPatterns.length; n++)
    if (bitPatterns[n] & bitsSoFar != 0)
        // overlap of bitPatterns[n] with an earlier pattern
        bitsSoFar |= bitPatterns[n]

Links als Übung:

• Ändern Sie den Algorithmus, um auch die Überlappung eines Bitmusters mit einem späteren zu identifizieren

• Berechnen Sie das Bitmuster für ein Intervall in O (1).

Wenn N Intervallpaare ganze Zahlen sind, können wir sie in O (n) erhalten.

Sortieren Sie es nach der ersten Nummer im Paar und dann nach der zweiten Nummer. Wenn alle Ganzzahlen sind, können wir die Bucket-Sortierung oder die Radix-Sortierung verwenden, um sie nach O (n) zu erhalten.

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

Dann kombinieren Sie eins nach dem anderen,

{1,3}

{1,4} mit Überlappung {1,3} und {2,4}

{1,4}, {5,10}

{1,4}, {5,10}, {12,14}

{1,4}, {5,10}, {12,15} mit Überlappung {12,14} und {13,15}

Die Kombination würde O (N) Zeit dauern

Hier ist eine O(N lg N)Implementierung in Java, die die Antwort von @Nikita Rybak erweitert.

Meine Lösung findet jedes Intervall, das sich mit mindestens einem anderen Intervall überschneidet, und zählt beide als überlappende Intervalle. Zum Beispiel überlappen sich die beiden Intervalle (1, 3)und (2, 4)die ursprüngliche Frage von OP. In diesem Fall gibt es also zwei überlappende Intervalle. Mit anderen Worten, wenn sich Intervall A mit Intervall B überschneidet, füge ich sowohl A als auch B zu der resultierenden Menge von Intervallen hinzu, die sich überlappen.

Betrachten wir nun die Intervalle (1, 100), (10, 20)und (30, 50). Mein Code wird Folgendes finden:

[ 10,  20] overlaps with [  1, 100]
[ 30,  50] overlaps with [  1, 100]

Resulting intervals that overlap with at least one other interval:
[  1, 100]
[ 30,  50]
[ 10,  20]

Um zu verhindern, (1, 100)dass zweimal gezählt wird, verwende ich ein Java Set, das nur eindeutige Intervallobjekte enthält.

Meine Lösung folgt dieser Gliederung.

1. Sortieren Sie alle Intervalle nach Startpunkt. Dieser Schritt ist O(N lg N).
2. Behalten Sie intervalWithLatestEnddas Intervall mit dem letzten Endpunkt im Auge.
3. Durchlaufen Sie alle Intervalle in der sortierten Liste. Wenn sich ein Intervall mit überschneidet intervalWithLatestEnd, fügen Sie beide zu einem Satz hinzu. Aktualisieren Sie, intervalWithLatestEndwenn nötig. Dieser Schritt ist O(N).
4. Geben Sie das Set zurück (und konvertieren Sie es bei Bedarf in eine Liste).

Die Gesamtlaufzeit beträgt O(N lg N). Es erfordert einen Ausgabesatz von Größe O(N).

Implementierung

Um einem Satz Intervalle hinzuzufügen, habe ich eine benutzerdefinierte Intervallklasse erstellt equals(), die erwartungsgemäß überschrieben wird.

class Interval {
    int start;
    int end;
    Interval(int s, int e) { 
        start = s; end = e; 
    }

    @Override
    public String toString() {
        return String.format("[%3d, %3d]", start, end);
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + start;
        result = prime * result + end;
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Interval other = (Interval) obj;
        if (start != other.start)
            return false;
        if (end != other.end)
            return false;
        return true;
    }
}

Und hier ist der Code, der den Algorithmus ausführt:

private static List<Interval> findIntervalsThatOverlap(List<Interval> intervals) {

    // Keeps unique intervals.
    Set<Interval> set = new HashSet<Interval>();

    // Sort the intervals by starting time.
    Collections.sort(intervals, (x, y) -> Integer.compare(x.start, y.start));

    // Keep track of the interval that has the latest end time.
    Interval intervalWithLatestEnd = null;

    for (Interval interval : intervals) {

        if (intervalWithLatestEnd != null &&
            interval.start < intervalWithLatestEnd.end) {

            // Overlap occurred.
            // Add the current interval and the interval it overlapped with.
            set.add(interval); 
            set.add(intervalWithLatestEnd);

            System.out.println(interval + " overlaps with " +
                               intervalWithLatestEnd);
        }

        // Update the interval with latest end.
        if (intervalWithLatestEnd == null ||
            intervalWithLatestEnd.end < interval.end) {

            intervalWithLatestEnd = interval;
        }
    }
    // Convert the Set to a List.
    return new ArrayList<Interval>(set);
}

Testfälle

Hier ist ein Testfall, in dem die ursprünglichen Intervalle des OP ausgeführt werden:

public static void testcase() {

    List<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    intervals.add(new Interval(1, 3));
    intervals.add(new Interval(12, 14));
    intervals.add(new Interval(2, 4));
    intervals.add(new Interval(13, 15));
    intervals.add(new Interval(5, 10));


    result = findIntervalsThatOverlap(intervals);
    System.out.println("Intervals that overlap with at least one other interval:");
    for (Interval interval : result) {
        System.out.println(interval);
    }
}

mit dem Ergebnis:

[  2,   4] overlaps with [  1,   3]
[ 13,  15] overlaps with [ 12,  14]
Intervals that overlap with at least one other interval:
[  2,   4]
[  1,   3]
[ 13,  15]
[ 12,  14]

Zum Schluss noch ein fortgeschrittener Testfall:

public static void testcase() {

    List<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    intervals.add(new Interval(1, 4));
    intervals.add(new Interval(2, 3));
    intervals.add(new Interval(5, 7));
    intervals.add(new Interval(10, 20));
    intervals.add(new Interval(15, 22));
    intervals.add(new Interval(9, 11));
    intervals.add(new Interval(8, 25));
    intervals.add(new Interval(50, 100));
    intervals.add(new Interval(60, 70));
    intervals.add(new Interval(80, 90));


    result = findIntervalsThatOverlap(intervals);
    System.out.println("Intervals that overlap with at least one other interval:");
    for (Interval interval : result) {
        System.out.println(interval);
    }
}

mit dem Ergebnis:

[  2,   3] overlaps with [  1,   4]
[  9,  11] overlaps with [  8,  25]
[ 10,  20] overlaps with [  8,  25]
[ 15,  22] overlaps with [  8,  25]
[ 60,  70] overlaps with [ 50, 100]
[ 80,  90] overlaps with [ 50, 100]
Intervals that overlap with at least one other interval:
[  2,   3]
[  8,  25]
[  9,  11]
[ 50, 100]
[  1,   4]
[ 15,  22]
[ 10,  20]
[ 60,  70]
[ 80,  90]

Es ist schon eine Weile her, seit ich es verwendet habe, aber die Lösung, die ich verwendet habe, war eine Ableitung des in Einführung in Algorithmen beschriebenen rot-schwarzen Baums, der als Intervallbaum bezeichnet wird. Es ist ein Baum, der nach Intervallstart sortiert ist, sodass Sie schnell (binäre Suche) zuerst den ersten in Frage kommenden Knoten finden können. IIRC, die Knoten wurden nach einer Eigenschaft geordnet, mit der Sie aufhören können, den Baum zu "durchlaufen", wenn die Kandidatenknoten nicht mit Ihrem Intervall übereinstimmen können. Ich denke, es war eine O (m) -Suche, wobei m die Anzahl der übereinstimmenden Intervalle ist.

Ich habe diese Implementierung gefunden .

Brett

[Bearbeiten] Wenn Sie die Frage noch einmal lesen, haben Sie sie nicht gestellt. Ich denke, dies ist die beste Implementierung, wenn Sie eine Liste von (zum Beispiel) Besprechungen haben, die bereits in Konferenzräumen geplant sind (die dem Baum hinzugefügt werden), und Sie möchten herausfinden, welche Räume für eine Besprechung mit einem neuen Start und einer neuen Dauer noch verfügbar sind (der Suchbegriff). Hoffentlich hat diese Lösung jedoch eine gewisse Relevanz.

Dieses Problem kann auf das Elementeindeutigkeitsproblem reduziert werden.

Die Eindeutigkeit von Elementen hat eine Untergrenze von Omega (n log n) (Anzahl der Vergleiche), daher können Sie es nicht besser machen.

Sie können die Liste einmal durchgehen und eine Hash-Tabelle aller bisher aufgetretenen Intervalle führen. Wenn ein Eingabeintervall Teil eines Intervalls aus der Hash-Tabelle ist, führen Sie es in das Intervall der Hash-Tabelle ein. Markieren Sie die nicht primitiven Intervalle (zusammengeführte Intervalle, die aus mehr als einem Intervall bestehen).

Dann gehen Sie die Liste ein zweites Mal durch und prüfen für jedes Intervall in der Hash-Tabelle, ob sie in einem zusammengeführten Intervall enthalten ist oder nicht.

Ich weiß nicht, ob es O (N) ist, aber es ist viel besser als O (N ^ 2).