Lifeguards

题目描述

农夫约翰为他的奶牛开了一个游泳池，认为这能帮助它们放松并产更多的奶。 为了确保安全，他雇了 $N$ 头奶牛作为救生员，每头奶牛都有一个班次，覆盖一天中某个连续的时间区间。为简化起见，游泳池每天从时间 $t=0$ 开放到时间 $t=1000$，因此每个班次都可以用两个整数来描述，分别表示一头奶牛开始和结束值班的时间。例如，一个救生员从时间 $t = 4$ 开始到时间 $t = 7$ 结束，她覆盖了 3 个单位的时间（注意端点是时间上的“点”）。 不幸的是，农夫约翰雇的救生员比他能负担的多了 1 个。已知他必须恰好解雇一名救生员，问剩余救生员的班次最多还能覆盖多少时间？若某段时间内至少有一名救生员在场，则该时间区间被认为是被覆盖的。

输入格式

第一行输入 $N$（$1 \leq N \leq 100$）。接下来 $N$ 行每行用两个位于 $0 \ldots 1000$ 范围内的整数描述一名救生员的班次，分别表示该救生员班次的起始与结束时刻。所有这些端点互不相同。不同救生员的班次可能重叠。

输出格式

输出一个数字，表示农夫约翰解雇 1 名救生员后，剩余班次仍能覆盖的最大时间长度。

3
5 9
1 4
3 7

7

提示

题目来源：Brian Dean

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze