Algorithmen[5]#4

[Tankwart]

Kann mir jemand sagen was der Trick an dem Algorithmus ist?
Hab zwar einen funktionierenden der sogar schneller als die angegebene Schranke ist, aber leider nur wenn der Zug weniger als ~10 Plätze hat

[Thomas]

meine idee bis jetzt wäre:
erstmal die n paare nach den startbahnhöfen zu sortieren. dann nimmt man die ersten m einträge des sortierten arrays und speichert es in nem extra array und die restlichen n - m einträge in einem andren array. nun sortiert man das array mit den ersten m startbahnhöfen nach den zielbahnhöfen, muss aber vorher irgendwie den sitzplatz speichern. also den eintrag im array. wenn man nach den zielbahnhöfen sortiert hat müssen die sitzplätze noch vorhanden sein. nun vergleicht man den ersten zielbanhof mit dem ersten startbahnhof des arrays der übrigen n-m einträge. ist der startbahnhof größer gleich dem zielbahnhof, kann dieser fahrgast auch mitfahren und erhält beim aussteigen des fahrgasts mit dem zielbahnhof dessen sitzplatz. das ganze wiederholt man dann mit dem 2. zielbahnhof und dem 2. startbahnhof bis man alle startbahnhöfe des n-mten arrays mit den zielbahnhöfen des andren arrays verglichen hat. sollte einmal ein startbahnhof kleiner dem zielbahnhof sein, könnte der fahrgast nicht mitfahren und man könnte nicht alle wünsche erfüllen. so würde ich den algorithmus machen. der größte aufwand wäre dann das sortieren der n paare nach den startbahnhöfen was in O(n log n) läge. dass sortieren der zielbahnhöfe wäre dann nur noch O(m log m) und das vergleichen der ziel mit den startbahnhöfen wäre in O(n - m). Probleme hätte ich noch mit dem speichern der sitzplätze, was man vllt dadurch lösen könnte dass man in den arrays noch jedem element einen zusätzlichen leeren speicherplatz gibt, in dem man dann den sitzplatz speichert. auch noch problematisch wäre wenn n > 2m ist. dann müsste man das rest array mit den n - m reservierungen nochmal aufteilen und dann hätte man drei arrays die man checken müsste bzw beliebig viele.
was meint ihr dazu? jemand vllt ne bessere idee

[Chris]

kannst da nochmal was genaueres schreiben ? ich komm einfach net drauf krieg immer eine zu hohe laufzeit

[Thomas]

hm bin eh nicht sicher ob das stimmt das wie gesagt net passt wenn n > 2m da müsste man das 2. array nochmals aufteilen. ich werds mir später nochma anschauen, falls mir noch was einfallen sollte, schreib ichs rein. aba aknnst ja ma schreiben wie dus gemacht hast

[Thomas]

sry für den doppelpost, aber dass man auch sieht dass ich wasneues geschrieben habe:
@ chris kann dir mal schreiben wie ich mir den anfang so gedacht habe, aba keine gewähr für die korrektheit bin selbst nur am rumfummeln und rummraten und wär für hilfe dankbar:
also zunächst hätte ich eine klasse Reservierungen erstellt, die als Attribut jeweils einen Start- und einen Zielbahnhof besitzt.
die n Reservierungen sind dann also eigene Objekte und werden in einem 2-dimensionalem array gespeichert (für jedes element den zusätzlichen speicherplatz um die reservierungsnummer hinzuzufügen)
dann sortiert man das array nach den startbahnhöfen ich würds mit mergesort machen und selbst implementieren also bei jedem reservierungsobjekt auf den startbahnhof zugreifen und diese dann vergleichen. beim sortierten array fügt man den ersten m elementen die nummerierung von 1 - m zu, als nummerierung für den sitzplatz. jetzt würde ich die ersten m elemente in einem neuen array speichern und die restlichen n-m elemente in einem anderen. das array mit den ersten m elementen würde ich nun nach den zielbahnhöfen sortieren um zu wissen wer wo aussteigt. jetzt kann man die zielbahnhöfe der ersten m fahrgäste mit den startbahnhöfen der restlichen reservierungen vergleichen. also etwa c[0].zielbahnhof <= d[0].startbahnhof. wenn diese bedingung erfüllt ist kann der neue fahrgast mitfahren und den sitzplatz des aussteigenden übernehmen. falls m >= n-m ist reichen diese vergleiche aus. falls nicht müsste man von n-m nochmals m abziehn nachdem man diese 2. anzahl an m fahrgästen mit der ersten anzahl an m fahrgästen verglichen hätte und alle fahrgäste der 2. m reservierungen einen sitzplatz erhalten würden. wie man das aber alles genau implementiert oder ob das überhaupt so passt, weiß ich leider selbst nicht. das is nur die idee wie ichs mir mal gedacht habe, was besseres ist mir leider noch nicht eingefallen.