P8180 - Lifeguards

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：5 通过：1

Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time until time on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time and ending at time covers three units of time (note that the endpoints are "points" in time).

Unfortunately, Farmer John hired more lifeguards than he has the funds to support. Given that he must fire exactly lifeguards, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.

The first line of input contains

and

(

K \leq N \leq 100, 000, 1 \leq K \leq 100

). Each of the next

lines describes a lifeguard in terms of two integers in the range

0 \dots 109

, giving the starting and ending point of a lifeguard's shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires

lifeguards.

In this example, FJ should fire the lifeguards covering

1 \dots 8

and

7 \dots 15

USACO 2018 January Contest, Platinum

8180: Lifeguards

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签