Dies ist ein Problem, das auf der Suche nach der Größe der maximal verschachtelten Intervalle basiert.
Es gibt viele Intervalle, die jeweils durch ein Paar mit einem Anfangs- und einem Endpunkt (si, ei) definiert sind. Zwei Intervalle i1 und i2 werden als verschachtelt bezeichnet, wenn i2 vollständig innerhalb von i1 liegt. Beispiel:- (2,6) und (3,4) sind verschachtelt, da (3,4) ein Teil von (2,6) ist. In ähnlicher Weise werden k Intervalle i1, i2, i3....ik als verschachtelt bezeichnet, wenn i2 innerhalb von i1 liegt, i3 innerhalb von i2 liegt, ...und so weiter. Bestimme die Größe der größten Menge von Intervallen aus den gegebenen Intervallen, so dass alle Intervalle in dieser Menge eine Verschachtelung ergeben können.
Ich habe mir das folgendermaßen vorgestellt:- Nehmen wir z.B. (0,7) (0,5) (1,21) (1,9) (2,8) (2,4) (3,20) (4,16) (5,15) (6,21) Sortieren Sie es so, dass a[i-1]<=a[i] && b[i-1]>=b[i] Dann beginnen wir mit dem ersten Intervall eine verknüpfte Liste... wenn das nächste Intervall innerhalb eines Intervalls liegt, bewegen wir uns den Knoten hinunter und durchlaufen den Graphen, der unterhalb des Knotens erstellt wurde (anders als die Hauptliste)... Wir speichern den Zeiger des Knotens mit der höchsten Ebene in diesem Graphen, auf den das neue Intervall passen kann... und traversieren weiter in der verknüpften Liste, um zu sehen, unter wen das aktuelle Intervall fällt... schließlich haben wir einen Zeiger auf einen Knoten, mit dem wir das aktuelle Intervall verbinden müssen... und vergleichen die Ebene dieses Knotens mit der maximalen Ebene, die wir bereits haben..... Der endgültige Wert der maximalen Ebene ist die Größe der maximal verschachtelten Intervalle...
Die Komplexität der obigen Lösung ist wahrscheinlich:- O(n(k+l) + nlogn)
Ich denke, es ist schwierig, es auf diese Weise zu erhalten, aber ich habe keine andere Option ... wenn jemand einen anderen Algorithmus, um es zu lösen... bitte posten, weil mein Algorithmus wird viel länger dauern, um zu implementieren (viele Datenstrukturen beteiligt) ... danke!!!
