"Maximum" Überlappungsintervall Paar in O (nlog (n))

Question

Problem Statement

Eingang Satz von n Intervallen zu finden; {[s_1, t_1], [s_2, t_2], ..., [s_n, t_n]}.

Ausgabe Paar Intervalle; {[s_i, t_i], [s_j, t_j]}, mit der maximalen Überlappung zwischen allen Intervallpaaren.

Beispiel

Eingangsintervalle: {[1, 10], [2, 6], [3,15], [5, 9]}

-> Es gibt mögliche 6-Intervall Paare. Unter diesen Paaren, [1,10] & [3,15] hat die größte mögliche Überlappung von 7.

Ausgabe: {[1,10], [3,15]}

Ein naiver Algorithmus eine Brute-Force-Methode sein, bei der alle n Intervalle miteinander verglichen werden, während der aktuelle maximale Überlappungswert verfolgt wird. Die Zeitkomplexität wäre für diesen Fall O (n^2).

Ich konnte viele Verfahren in Bezug auf Intervall Bäume, maximale Anzahl von überlappenden Intervallen und maximaler Satz von nicht-überlappenden Intervallen, aber nichts über dieses Problem finden. Vielleicht wäre ich in der Lage, die in den obigen Algorithmen gegebenen Ideen zu verwenden, aber ich konnte mir keine vorstellen.

Ich habe viele Stunden damit verbracht, eine gute Lösung zu finden, aber ich denke, ich brauche an dieser Stelle Hilfe.

Alle Vorschläge helfen!

Answer 1

Sortieren Sie zuerst die Intervalle: zuerst nach linkem Endpunkt in aufsteigender Reihenfolge, dann — als sekundäres Kriterium — nach rechtem Endpunkt in absteigender Reihenfolge. Für den Rest dieser Antwort nehme ich an, dass die Intervalle bereits in sortierter Reihenfolge sind.

Nun gibt es zwei Möglichkeiten für das, was die maximal mögliche Überlappung sein könnte:

• es zwischen einem Intervall und einem späteren Intervall sein kann, dass sie vollständig bedeckt.
• es kann zwischen einem Intervall und dem nächsten Intervall sein, dass es nicht vollständig abdecken.

Wir beide Fälle in O (n ) Zeit durch Iterieren über die Intervalle, die Verfolgung der folgenden abdecken kann:

• die größte Überlappung wir bisher gesehen haben, und die entsprechende Paar von Intervallen.
• das letzte Intervall, das wir gesehen haben, nennen Sie es L, das von keinem seiner Vorgänger vollständig abgedeckt wurde.(Die wichtigste Erkenntnis ist, dass wir dank der Reihenfolge der Intervalle leicht feststellen können, ob ein Intervall vollständig von einem seiner Vorgänger — abgedeckt ist, und daher, wenn wir L — aktualisieren müssen, einfach überprüfen, ob es vollständig ist von der aktuellen L abgedeckt. So wir L up-to-date in O (1) Zeit halten können.)

und Berechnen jedes der Überlappungsintervall mit L.

So:

result := [] 
max_overlap := 0 
L := sorted_intervals[1] 
for interval I in sorted_intervals[2..n]: 
    if L.right - I.left >= max_overlap: 
     result := [L, I] 
     max_overlap := L.right - I.left 
    if I.right > L.right: 
     L := I 

So Die Gesamtkosten sind die Kosten für die Intervalle der Sortieranlage, die O wahrscheinlich zu sein ist (n log n) Zeit, sondern kann O (n) sein Wenn Sie Bucket-Sort oder Radix-Sort oder ähnliches verwenden können.