Algorithmen Übungen WS 2008/2009

Harald B. P. Shell ist der Manager einer Tankstelle. Harald will, dass seine Tankstelle rund um die Uhr geöffnet ist. Da er nicht selbst die ganze Zeit an der Kasse stehen kann, sucht er Mitarbeiter, die jeden Tag eine bestimmte Arbeitsschicht übernehmen. Um Verwaltungskosten zu sparen, sollen möglichst wenige Arbeitskräfte eingestellt werden.

Harald hat viele Bewerbungen bekommen, in denen potentielle Mitarbeiter ihre Wunschzeiten für eine Schicht angegeben haben. Beispielsweise möchte ein Bewerber gerne jeden Tag zwischen 10 Uhr und 12 Uhr arbeiten, ein anderer Bewerber von 23 Uhr bis 2 Uhr des nächsten Tages. Jeder Bewerber würde allerdings auch akzeptieren, wenn er nur für einen Teil seiner Wunscharbeitszeit angestellt würde.

Sie haben die Aufgabe, zu bestimmen, wie viele Arbeitskräfte Harald mindestens einstellen muss, damit seine Tankstelle rund um die Uhr besetzt ist und er selbst nicht mehr an der Kasse stehen muss.

Eingabe

Die erste Zeile der Eingabe enthält die Zahl n der Bewerbungen (2 ≤ n ≤ 1000). Die folgenden n Zeilen enthalten für jeden Bewerber die gewünschte Startzeit gefolgt von der gewünschten Endzeit im Format HH:MM (0 <= HH <= 23, 0 <= MM <= 59). Sie können annehmen, dass die Startzeit ungleich der Endzeit ist.

Ausgabe

Geben Sie die minimale Anzahl Bewerber aus, die eingestellt werden müssen, sodass die Tankstelle rund um die Uhr besetzt ist. Sie können annehmen, dass nur Testfälle gegeben werden, für die eine Lösung existiert.

Beispiel 1

Eingabe:
7
09:00 18:00
18:01 00:00
00:01 08:59
08:00 14:00
14:00 20:00
19:55 02:00
02:00 08:00
Ausgabe:
4

Beispiel 2

Eingabe:
4
10:00 16:00
16:00 22:00
22:00 04:00
04:00 10:00
Ausgabe:
4

Im ersten Beispiel reichen die drei ersten Bewerber nicht aus, da dann z. B. von 18:00 bis 18:01 niemand die Kasse besetzen würde. Die letzten vier Bewerber können dagegen z. B. folgendermaßen eingesetzt werden: 08:00 bis 14:00 Bewerber 4, 14:00 bis 19:57 Bewerber 5, 19:57 bis 02:00 Bewerber 6 und 02:00 bis 08:00 Bewerber 7 (und nun beginnt wieder Bewerber 4 seine Schicht).