Algorithmen[9]#2

[elTybbq]

zur c) würde das mit Sortieren lösen aber gehts vielleicht auch irgendwie in Linearzeit?

[Christian S.]

Also ich habe es auch nur in O(n log n) .

[Chrisss]

Wie habt ihr bei diesem Algorithmus angesetzt?
Ich dachte eiglenitch man kann das in abgeänderter Form wie in der Vorlesung zu Intervall-Graphen realisieren, aber das Array A speichert ja nun direkt die Intervalle, also wohl in Form von (startpunkt,endpunkt) Toupel.
Habt ihr aus dem Array dann die Punkte einzeln rausgezogen und die geänderte Form aus der Vorlesung gemacht?
Oder funktioniert euer Ansatz völlig anders?

[Cauchy]

Wie wäre es den DFS Algorithmus zu benutzen und die methoden init, root, backtrack, traversetreeedge zu überschreiben?

[Thomas]

das ganze is ein ähnliches problem wie damals mit den zugreservierungen glaub ich, würde es also auch mit sortieren lösen

[Christian S.]

Jop, lässt sich imo fast 1:1 wie Zugreservierung lösen. Einfach sortieren und schauen, ob man über den bisherigen Bereich zum aktuellen Intervall kommt, falls ja, vergrößert man den Bereich, falls nein, neuer Bereich. Jedenfalls habe ich es so gemacht . Der "Rest" außerhalb des Sortierens liegt bei mir damit in O(n).