Lifeguards

题目描述

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

输入格式

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

输出格式

请输出一个整数，表示在农夫约翰解雇 1 名救生员后，最多仍能被覆盖的时间总量。

3
5 9
1 4
3 7

7

提示

题目来源：Brian Dean

标签: USACO|2018|Silver

来源

USACO|2018|Silver