Programozás‎ > ‎Feladatok‎ > ‎

Tehénfejés

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