Vorlesungsplanung

Gegeben $n$ Vorlesungen mit Start- und Endzeit $(s_i,e_i)$.

Aufgabe: Finde das kleinste $k$ und eine Zuweisung der Vorlesungen zu $k$ Hörsälen, so dass alle Vorlesungen in $k$ Hörsälen abgehalten werden können.

Idee 1: Wähle eine maximal große Menge an Vorlesungen, die sich alle gleichzeitig überlappen. Weise diesen Vorlesungen in beliebiger Reihenfolge jeweils einen eigenen Hörsaal zu. Iteriere mit den noch nicht zugewiesenen Vorlesungen, nutze dabei neue Hörsäle, falls die geplante Zuweisung mit den aktuellen Hörsälen nicht möglich ist.

Idee 2: Sortiere die Vorlesungen absteigend nach Dauer. Weise die längste Vorlesung Hörsaal 1 zu. Nun füge, absteigend nach Länge, weitere Vorlesungen zu Hörsaal 1 zu, so lange keine Überlappung entsteht. Iteriere nun mit je einem neuen Hörsaal und den verbliebenen Vorlesungen bis alle zugewiesen sind.

Idee 3: Gehe die Vorlesungen aufsteigend nach Startzeit durch. Weise die erste Vorlesung Hörsaal 1 zu. Iteriere nun und weise die aktuelle Vorlesung immer dem aktuell freien Hörsaal mit der kleinsten Nummer zu.