Lösung zur Aufgabe P-23:

Gegeben ist eine Menge A = { (s1,e1) ,..., (sn,en) } von Anträgen,
eine Ressource (etwa einen Raum) jeweils vom Zeitpunkt si bis ei zu
benutzen. Es sollen alle Anträge gewährt werden, aber dabei möglichst
wenig Resourcen verwendet werden.

Eine Lösung ist also eine Familie von disjunkten Mengen B1,...,Bk
derart dass deren Vereinigung die ganze Menge {1,...,n} ist, und dass
für jedes i die Intervalle in Bi sich nicht überschneiden.  Die Anzahl
k ist dabei zu minimieren.

Ein greedy-Algorithmus zur Lösung dieses Problems ist der folgende:
Wir benutzen folgende Variablen:

  k :  Anzahl der Räume
  B(j) für j <= k: Belegung der Räume
  E(j) für j <= k: Endzeitpunkt des letzten Antrags in B(j)

Die Menge A sei so sortiert, dass s1 <= s2 <= ... <= sn ist.
(Greedy:behandle stets den frühest startenden Antrag zuerst.)

Am Anfang setze k:=1, B(1) := {1} und E(1) := e1.
Anschliessend für i := 2 bis n
  Falls E(j) > si für alle j <= k  %% Antrag i passt in keinen Raum
        dann setze k := k+1, B(k) := {i} und E(k) := e_i
        sonst wähle j <= k mit E(j) <= s_i maximal (greedy)
              und setze B(j) = B(j) + {i} und E(j) = ei


Das allgemeine Problem, mit dem der Algorithmus während des Ablaufes
konfrontiert ist, sieht also so aus: ich habe k+1 Räume, von denen der
Raum j ab Zeitpunkt Ej zur Verfügung steht, wobei E(k+1) = 0.  Dann
wählt der Algorithmus stets den Raum j, bei dem Ej am spätesten vor
der Startzeit si des gerade behandelten Antrags liegt.

Zu zeigen: dafür gibt es stets eine optimale Lösung, die mit der
greedy Auswahl des Algorithmus verträglich ist.

Sei also B1 , ... , Bk eine beliebige optimale Lösung. Sei j dasjenige
mit i in Bj, also derjenige Raum, dem Antrag i zugewiesen wurde. Sei
ferner j' derjenige Raum, dem der Algorithmus Antrag i zuweisen würde,
also der mit Ej' <= si maximal.

Ist j = j', so ist diese Lösung von der gesuchten Art. Andernfalls sei
i' der erste Antrag in Bj', dann ist si' >= si, also auch si' >= Ej.
Wir können also Bj und Bj' vertauschen, und erhalten eine Lösung
in der Antrag i so liegt, wie es der Algorithmus zuweisen würde.

Ferner wird dieses allgemeinere Problem durch eine Auswahl des
Algorithmus auf ein gleichartiges Teilproblem reduziert, das dann mit
der gleichen Strategie behandelt werden kann. Denn: Sei B eine
optimale Lösung des allgemeinen Problems, mit Anfangszeiten
E(1) , ... , E(k+1) und Anträgen i bis n, und j der Raum mit i in Bj.

Sei B' wie B, nur mit B'(j) = B(j) ohne {i}, dann ist B' eine optimale
Lösung des Teilproblems mit Anträgen i+1 bis n, und Anfangszeiten E'
genau wie E, nur E'(j) = ei. Aus einer besseren Lösung B'' für dieses
Teilproblem könnte ich nämlich durch Hinzufügen von i zu B''(j) auch
eine bessere Lösung für das ursprüngliche Problem gewinnen.

Also muss nach der ersten greedy Auswahl nur noch eine optimale Lösung
für das verbleibende Teilproblem gefunden werden, und dies kann mit
der gleichen Strategie erreicht werden. Daher findet der Algorithmus
stets eine optimale Lösung QED.