OI题库

【问题描述】

    我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，也就是说，我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

任务：

请写一个程序：

•  在输入文件中读入所有演讲的起始和终止时间；

•  计算最大的可能演讲总时间；

•  把结果写到输出文件中。

【输入文件】

在输入文件的第一行包括一个正整数 n ， n <= 10000 ，为所有的演讲的数目。

以下的 n 行每行含有两个由空格隔开整数 p 和 k ， 0 <= p < k <= 30000 。这样的一对整数表示一个演讲由时间 p 开始到时间 k 结束。

【输出文件】

输出文件只有唯一的一个整数，为最长的演讲总时间。

【样例输入】

rez.in

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

【样例输出】

rez.out

16