USACO 2018 January Contest, Bronze

问题 2：救生员

比赛已经结束。 分析模式

问题描述：

农夫约翰为他的奶牛们开设了一个游泳池，认为这能帮助它们放松并产更多的牛奶。为了确保安全，他雇佣了 N 头奶牛作为救生员，每头奶牛有一个工作时段，涵盖了一天中的某个连续时间区间。为了简化问题，假设游泳池每天从时间 t=0 开放直到 t=1000，因此每个时段可以通过两个整数来描述，分别是奶牛工作开始和结束的时间。例如，一头在 t=4 开始并在 t=7 结束的救生员覆盖了 3 个时间单位（注意端点是“点”）。

不幸的是，农夫约翰雇佣了比他能支付的救生员多出 1 个。鉴于他必须解雇恰好一名救生员，问题是：在剩下的救生员时段下，最大能覆盖多少时间？一个时间区间如果有至少一名救生员在场，就算是被覆盖的。

输入格式 (文件 lifeguards.in)：

• 第一行包含一个整数 N (1 ≤ N ≤ 100)，表示救生员的数量。
• 接下来的 N 行，每行包含两个整数，分别表示每个救生员的工作开始和结束的时间，范围是 0 到 1000，且所有的端点都不同。不同救生员的工作时段可能会重叠。

输出格式 (文件 lifeguards.out)：

输出一个整数，表示如果农夫约翰解雇一名救生员后，剩下的救生员能覆盖的最大时间。

样例输入：

3
5 9
1 4
3 7

样例输出：

7

题目分析：

• 题目要求计算，如果解雇一名救生员后，剩余救生员能覆盖的最大时间。
• 由于不同救生员的时段可能重叠，直接计算时要注意去重。
• 通过模拟每一名救生员被解雇后的覆盖时间，可以得出最大覆盖时间。

题目背景：

​Problem credits​: Brian Dean