Submit | All submissions | Best solutions | Back to list |
TANKST - Tankstelle |
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).
Added by: | Adrian Kuegel |
Date: | 2008-11-24 |
Time limit: | 1s-1.261s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |