网络传输

时间限制: 300 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0

题目描述

网络上的数据传输是共用数据线的,当一台主机发送传输请求时网络上有其他主机在发送数据,就不能成功发送只能等待。如果网络经常处于占用情况,平均等待时间过长,可能说明网络负载过重、拓扑结构不好或延时算法有问题。为了检测是否有这些问题,可以在服务器之间发送一些数据查看响应时间。

不过现在,我们姑且简化问题,将网络看做是一维的线段,各个主机看做线段上的点。当主机i向主机j发送数据时,i->j窗口所有的主机此时都不能发送数据。每次数据传输为1单位时间(由于网线上数据传输速度很快,不计距离影响)。

下面给出一组测试,求完成所有传输请求需要使用的最少的时间。

输入

多组测试数据,每组N+1行。

每组第一行数为题目描述中一组测试的请求数n

接下来n行,每行2个整数i,j,表示一次数据传输i->j。

1<=i,j<=N<=10000

输出

对于每组数据,输出一行,为最小用时。

输入样例

3
1 3
3 4
5 1

输出样例

3

相关推荐