Lifeguards

题目描述

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

输入格式

第一行输入包含 $N$ 和 $K$（$K \leq N \leq 100,000, 1 \leq K \leq 100$）。 接下来 $N$ 行中，每行用两个整数（范围为 $0 \ldots 10^9$）描述一名救生员的班次起点和终点。所有这些端点两两不同。不同救生员的班次可能重叠。

输出格式

请输出一个数，表示如果农夫约翰解雇 $K$ 名救生员，仍然可以被覆盖的最大时间长度。

3 2
1 8
7 15
2 14

12

提示

在这个例子中，FJ 应该解雇覆盖 $1 \ldots 8$ 和 $7 \ldots 15$ 的救生员。 题目来源：Brian Dean

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum