Gegeben sei eine Menge an Jobs, jeder mit einer Verarbeitungsdauer und einer Deadline. Die Jobs sind nacheinander auf einer Maschine auszuführen, es kann nur ein Job gleichzeitig ausgeführt werden. Wir möchten einen Plan entwickeln, d.h. eine Reihenfolge der Jobs, so dass jeder Job vor seiner Deadline fertig wird. Einen solchen Plan nennen wir "ausführbar".
Implementieren Sie in der Methode scheduleGreedy() ein Greedy-Verfahren, das - gegeben eine Menge von Jobs (als Array) - einen Plan zurückliefert. Dieser Plan soll ebenfalls ein Array von Jobs sein, wobei der vorderste Job zuerst ausgeführt wird, dann der nächste, usw. Fügen Sie in jeder Iteration ihrem Plan einen möglichst geeigneten nächsten Job hinzu. Beachten Sie:
- Ihre Methode sollte das originale Jobs-Array nicht verändern.
- Sie können annehmen, dass Dauer und Deadline eines Jobs jeweils nicht negativ sind. Der Beginn der Ausführung ihres Plans liegt bei $t=0$.
- Sollte kein ausführbarer Plan gefunden werden, soll ihre Methode eine ScheduleException werfen.
Ist Ihr Verfahren "optimal", d.h. findet es auch immer einen ausführbaren Plan wenn ein solcher Plan existiert? Falls nicht, geben Sie ein Gegenbeispiel. Fall ja, geben Sie eine informelle, aber schlüssige Begründung.