F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5185. -- [Usaco2018 Jan]Lifeguards

5185: [Usaco2018 Jan]Lifeguards

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 77  Solved: 45
[Submit][Status][Discuss]

Description

农夫约翰为他的奶牛们开了一个游泳池,他认为这将有助于他们放松和生产更多的牛奶。为确保安全,他请了N只
牛做救生员,每只牛都有一个工作时间,为一些连续的时间间隔为了简单起见,泳池每天从时间0打开到到10^9,
所以每个区间都可以用两个整数来描述,给定的这两个整数就是区间的开始和结束时刻。例如,一个救生员从t = 
4时开始工作和在t=7时结束,共覆盖三个时间单位(注意端点也是覆盖到的时间点)。但不幸的是,农夫约翰雇佣
了比它支付能力多出K个的救生员。他需要开除正好K个救生员,求出剩余的救生员最大能够覆盖多长的时间(一段
时间被覆盖当且仅当这时有至少一个救生员在工作)

Input

第一行包含N和K(K≤N≤10^5,1≤K≤100)

接下来的N行,每行描述一个在区间1...10^9上的救生员
给定这个救生员区间的开始和结束位置,其中有些救生员的区间可能会相交。

Output

 请输出一个数字,表示如果农夫约翰开除K个救生员,剩余救生员最大能够覆盖的时间长度

Sample Input

3 2
1 8
7 15
2 14

Sample Output

12
农夫约翰应该开除掉覆盖1...8和7...15两个区间的两个救生员

HINT

Source

Platinum 鸣谢WenDavid提供翻译

[Submit][Status][Discuss]

HOME Back