P1204 [USACO1.2] Milking Cows

Three farmers get up at $5$ a.m. every morning and go to the barn to milk three cows. The first farmer starts milking at $300$ seconds (counted from $5$ o'clock) and continues until $1000$ seconds. The second farmer starts at $700$ seconds and ends at $1200$ seconds. The third farmer starts at $1500$ seconds and ends at $2100$ seconds. The longest continuous time during which at least one farmer is milking is $900$ seconds (from $300$ seconds to $1200$ seconds), and the longest continuous time during which no one is milking (from the beginning of any milking to the end of all milking) is $300$ seconds (from $1200$ seconds to $1500$ seconds). Your task is to write a program that reads a list of working times for $n$ farmers milking $n$ cows and computes the following two values (both in seconds): 1. The longest interval during which at least one person is milking. 2. The longest interval during which no one is milking (counted from when milking begins).

The first line contains a positive integer $n$. The next $n$ lines each contain two non-negative integers $l, r$, representing one farmer’s start time and end time.

Output a single line with two integers separated by a single space: the two answers required by the problem.

Constraints For $100\%$ of the testdata, $1 \le n \le 5000$, $0 \le l \le r \le 10^6$. Problem translation from NOCOW. USACO Training Section $1.2$. Translated by ChatGPT 5