#P2439. [SDOI2005] 阶梯教室设备利用

[SDOI2005] 阶梯教室设备利用

题目描述

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

请写一个程序:

读入所有演讲的起始和终止时间,计算最大的可能演讲总时间。

输入格式

第一行包括一个正整数 nn,为所有的演讲的数目。

以下的 nn 行每行含有两个由空格隔开的整数 ppkk。这样的一对整数表示一个演讲由时间 pp 开始到时间 kk 结束。

输出格式

输出唯一的一个整数,为最长的演讲总时间。

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
16

提示

样例解释

可以选择第 33 个、第 55 个、第 66 个、第 1111 个、第 1212 个演讲,此时有最长的演讲总时间 1616

数据范围

1n1041\le n\le 10^40p<k3×1040\le p<k\le 3\times 10^4