P6699: 救生员
传统题
1.000s
时间限制
256MB
内存限制
7 提交
2 解决
【题目描述】
农场主约翰为他的奶牛开了一个游泳池，他认为这样可以帮助奶牛放松，产更多的牛奶。
为了确保安全，他雇佣了N头奶牛作为救生员，每头奶牛都有一个轮班，在一天中的某个连续时间间隔内轮班。为了简单起见，从时间t=0到时间t=1000，游泳池池每天都是开放的，因此每个班次可以用两个整数来描述，给出奶牛开始和结束班次的时间。例如，从时间t=4开始到时间t=7结束的救生员覆盖了三个时间单位（注意端点是时间上的“点”）。
不幸的是，Farmer John 雇佣的救生员比他有足够的资金支持多出 1 名。考虑到他必须解雇一名救生员，剩余救生员轮班的最大时间是多少？如果至少有一名救生员在场，则覆盖一段时间间隔。
输入格式（文件lifegards.in）：
输入的第一行包含N (1≤N≤100). 接下来的N行中的每一行都用0…1000范围内的两个整数来描述救生员，给出救生员移位的起点和终点。所有这些端点都是不同的。不同救生员的轮班可能会重叠。
输出格式（文件lifegards.out）：
请写一个数字，给出如果农民约翰解雇一名救生员，仍然可以覆盖的最大时间。
样本输入：
3
5 9
1 4
3 7
示例输出：
7