Mögliche Interview Frage: Wie Sie alle überlappenden Intervalle finden

Es ist keine Interviewfrage per se , da ich in meinem Projekt darauf gestoßen bin, aber ich dachte, es könnte eine anständige Frage sein.

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

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

die Antwort ist {1, 3}, {12, 14}, {2, 4}, {13, 15}. Beachten Sie, dass Sie sie nicht gruppieren müssen. Das Ergebnis kann also in einer beliebigen Reihenfolge wie im Beispiel angezeigt werden.

Ich warf gerade O (N) Zeit ein, weil der KMP-Algorithmus O (N) für die String-Suche benötigt. : D

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

Solutions Collecting From Web of "Mögliche Interview Frage: Wie Sie alle überlappenden Intervalle finden"

Wirf die Endpunkte der Intervalle in ein Array und markiere sie als Start- oder Endpunkte. Sortieren Sie sie, indem Sie die Bindungen brechen, indem Sie die Endpunkte vor den 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 

Dann iteriere die Liste und beobachte, wie viele Intervalle wir haben (dies entspricht der Anzahl der verarbeiteten Startpunkte minus der Anzahl der Endpunkte). Wann immer wir einen Startpunkt treffen, während wir bereits in einem Intervall sind, 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 ü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 das Sortieren der Hauptfaktor ist.

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

Dies ist zeitlich linear nach der anfänglichen Sortieroperation, die mit irgendeinem (n log n) Algorithmus durchgeführt werden könnte. Nicht sicher, wie du das schaffen würdest. Selbst die Operation “Duplikate herausfiltern” am Ende ist linear, wenn Sie die bereits sortierte Reihenfolge der Eingabe 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 Intervalle-on-the-line-Probleme besteht darin, sie nach dem Startpunkt zu sortieren und dann einfach von der ersten zur 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) } 

Nicht sicher über O (N), aber was ist, wenn wir sie zuerst nach der ersten Zahl in jedem Tupel sortieren und dann sequentiell diejenigen finden, bei denen die erste Zahl des Tupels größer ist als die größte in früheren Tupeln gesehene Zahl, was ebenfalls der Fall ist nicht überlappen mit dem nächsten Tupel.

Also würdest du zuerst bekommen:

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

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

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

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

Angenommen, der Unterschied zwischen Start- und Endpunkten ist klein, sagen wir <32. 1..32. Dann kann jedes Intervall als ein Bitmuster in einem 32-Bit-Wort geschrieben werden. zB [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 . Zwei Intervalle oder Kombinationen von Intervallen überlappen sich, wenn ihr bitweises AND nicht Null ist. z.B. [1,2] überlappt [1,3] weil 001&011 == 001 , ungleich Null. O (n) alg soll ein laufendes bitweises OR von bisher gesehenen Intervallen halten und AND jedes neue:

 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:

  • Modifiziere 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 Paare von Intervallen ganze Zahlen sind, dann können wir sie in O (n) bekommen.

Sortiere es nach der ersten Nummer in dem Paar und dann nach der zweiten Nummer. Wenn alle Ganzzahlen sind, können wir bucket sort oder radix sort 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 benötigen

Dieses Problem kann auf das Elementeindeutigkeitsproblem reduziert werden.

Element-Eindeutigkeit hat Omega (n log n) untere Grenze (Anzahl der Vergleiche zählen), so dass Sie nicht besser als das tun können.

Es ist schon eine Weile her, seit ich es benutzt habe, aber die Lösung, die ich benutzte, war eine Ableitung des Rot-Schwarz-Baums, der in Einführung in Algorithmen als Intervall-Baum bezeichnet wird. Es ist ein Baum, der nach Intervallstart sortiert ist, so dass Sie schnell (binäre Suche) zuerst den ersten auswählbaren Knoten auswählen können. IIRC, die Knoten wurden nach einer Eigenschaft geordnet, die es erlaubt, den Baum zu “laufen”, wenn die Kandidatenknoten nicht mit Ihrem Intervall übereinstimmen können. Also ich denke, es war O (m) Suche, wobei m die Anzahl der übereinstimmenden Intervalle ist.

Ich suche diese Implementierung gefunden .

Brett

[redigieren Sie] die Frage neu, das ist nicht, was Sie gebeten haben. Ich denke, das ist die beste Implementierung, wenn Sie eine Liste von (zB) bereits in Konferenzräumen geplanten Besprechungen haben (die zur Struktur hinzugefügt werden) und Sie möchten herausfinden, welche Räume noch für eine Besprechung mit einem neuen Start und einer neuen Dauer verfügbar sind (der Suchbegriff). Hoffentlich hat diese Lösung jedoch eine gewisse Relevanz.

 int find_no_overlapping_intervals(const vector< pair& a) { // a[i].first -> X ,a[i].second->Y // sort by start time sort.begin(a.begin(), a.end()); // maintain  in m map m; // i // for each point, we know its a[i].X >= a[0].X. ....a[i-1].X // there will be overlap, if for some j < i, a[j].Y >= a[i].X // lower_bound to find this.. it can be found in O(log(n)) as we use std::map for maintaining y int ans = 0; for (int i=0; i < a.begin(); i++) { auto sit = m.lower_bound(m.begin(), m.end(), a[i].first); auto eit = m.upper_bound(m.begin(), m.end(), a[i].first); for (auto it = sit; it != eit; it++) ans += it->second; m[a[i].second]++; } return ans; } 
 public ArrayList merge(ArrayList intervals) { ArrayList res = new ArrayList(); if (intervals == null || intervals.isEmpty()) return res; Comparator comparator = new Comparator() { @Override public int compare(Interval i1, Interval i2) { if (i1.start < i2.start) return -1; else if (i1.start > i2.start) return 1; else { if (i1.end < i2.end) return -1; else if (i1.end > i2.end) return 1; else return 0; } } }; Collections.sort(intervals, comparator); for (int i = 0; i < intervals.size(); i++) { Interval cur = intervals.get(i); if (res.isEmpty()) { res.add(cur); } else { Interval last = res.get(res.size() - 1); if (last.end >= cur.start) { last.end = Math.max(last.end, cur.end); } else { res.add(cur); } } } return res; } 

Dies ist eine einfache O(N*log(N)) Implementierung in Python:

 def overlapping(intervals): last = (-1, -1) overlapping = set() for curr in sorted(intervals, key=lambda p: p[0]): if curr[0] < last[1]: overlapping.add(curr) overlapping.add(last) last = max(curr, last, key=lambda p: p[1]) return list(overlapping - set((-1, -1))) print overlapping([(1, 3), (12, 14), (2, 4), (13, 15), (5, 10)]) #=> [(1, 3), (13, 15), (2, 4), (12, 14)] 

Zuerst sortiert er die Intervalle nach der Endzeit, vergleicht dann für jedes Intervall die Anfangszeit mit der größten gefundenen Endzeit, und wenn sie kleiner ist, bedeutet dies, dass es eine Überlappung gibt.

Der Sortierabschnitt ist derjenige, der die meiste Zeit benötigt, daher ist die letzte Komplexität N*log(N) .

Implementierung in C ++ mit einem Sweepline-Algorithmus ( O(N log N) ):

 #include  #include  #include  #include  #include  struct Interval { double start; double end; }; //----------------------------------------------------------------------------- // Enum to qualify event: Start/End of "segment-line" enum class EIntervalState { Start, End }; //----------------------------------------------------------------------------- // Events used for collision detection struct Event { double pos; EIntervalState state; std::size_t id; }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should overlap class LessIncludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state); } }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should not overlap class LessExcludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state); } }; //----------------------------------------------------------------------------- std::vector MakeEvents(const std::vector& intervals) { std::vector res; std::size_t id = 0; for (const auto& interval : intervals) { res.push_back({interval.start, EIntervalState::Start, id}); res.push_back({interval.end, EIntervalState::End, id}); ++id; } return res; } //----------------------------------------------------------------------------- template  std::vector> ComputeOverlappingIntervals(std::vector&& events, Less less) { std::sort(events.begin(), events.end(), less); std::set activeIds; std::vector> res; for (const auto& event : events) { switch (event.state) { case EIntervalState::Start: { for (const auto& id : activeIds) { res.emplace_back(std::minmax(event.id, id)); } activeIds.emplace(event.id); break; } case EIntervalState::End: { activeIds.erase(event.id); break; } } } return res; } 

Und benutze es:

 int main() { const std::vector intervals = { {1, 3}, {12, 14}, {2, 4}, {13, 15}, {5, 10} }; for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals), LessExcludeLimit{})) { std::cout < < "intervals " << p.first << " and " << p.second << " overlap\n"; } } 

Demo

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 überlappt, und zählt sie als überlappende Intervalle. Zum Beispiel überlappen sich die zwei Intervalle (1, 3) und (2, 4) von der ursprünglichen Frage von OP, und so gibt es in diesem Fall 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 überlappenden Intervallen hinzu.

Betrachten Sie 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, dass (1, 100) doppelt gezählt wird, verwende ich ein Java- Set , das nur eindeutige Interval-Objekte enthält.

Meine Lösung folgt diesem Umriss.

  1. Sortiere alle Intervalle nach Startpunkt. Dieser Schritt ist O(N lg N) .
  2. Verfolgen Sie intervalWithLatestEnd , das Intervall mit dem letzten Endpunkt.
  3. Iteriere über alle Intervalle in der sortierten Liste. Wenn sich ein Intervall mit intervalWithLatestEnd überlappt, fügen Sie beide zu Set hinzu. Aktualisieren Sie intervalWithLatestEnd bei Bedarf. Dieser Schritt ist O(N) .
  4. Gebe das Set zurück (und wandle es bei Bedarf in eine Liste um).

Die Gesamtlaufzeit ist O(N lg N) . Es benötigt einen Ausgang Satz der Größe O(N) .

Implementierung

Um Intervalle zu einer Menge hinzuzufügen, habe ich eine benutzerdefinierte Interval-class erstellt, die erwartungsgemäß equals() überschreibt.

 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 findIntervalsThatOverlap(List intervals) { // Keeps unique intervals. Set set = new HashSet(); // 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(set); } 

Testfälle

Hier ist ein Testfall, der die ursprünglichen Intervalle des OPs ausführt:

 public static void testcase() { List intervals = null; List result = null; intervals = new ArrayList(); 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] 

Schließlich ist hier ein fortgeschrittener Testfall:

 public static void testcase() { List intervals = null; List result = null; intervals = new ArrayList(); 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] 

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

Dann gehen Sie ein zweites Mal über die Liste 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).