Három gazda minden reggel 5-kor kel, hogy megfejje a teheneket. Az első gazda a kezdési időpontja 300 (5:00 után eltelt másodpercekben mérve), befejezési időpontja 1000. A második gazda 700-kor kezd és 1200-kor végez. Végül a harmadik gazda 1500-kor kezd és 2100-kor végez.
A leghosszabb időintervallum, amikor legalább az egyik gazda dolgozik 900 másodperc (300-tól 1200-ig). A leghosszabb időszak, amikor senki nem dolgozik 300 másodperc (1200-tól 1500-ig).
A következőkben N gazdára kell megkeresnünk ezeket az értékeket.
Feladat
Írjunk programot, ami a kezdési és befejezési idők N (1 <= N <= 5000) hosszú listája alapján megadja - a leghosszabb időintervallumot, amikor legalább egy tehenet fejnek;
- a leghosszabb időintervallumot, amikor nem fejnek tehenet.
Bemenet
A bemenet első sora N értékét tartalmazza. Ezután N sorban kezdési és befejezési időpontok következnek, másodpercben megadva (az 5:00 pillanatot tekintve 0-nak).
Kimenet
Két szám, szóközzel elválasztva: a leghosszabb intervallum, amikor legalább egy tehenet fejtek, és a leghosszabb, amikor egyet sem.
Példa
Bemenet |
Kimenet |
3 300 1000 700 1200 1500 2100 | 900 300
|
Tesztadatok
Címkék
A feladat forrása: USACO training material, Milking Cows
Algoritmusok:
megoldás |