PID498 / [CSAPC 08]Boat
题目描述

埃及的尼罗河上有很多游轮,虽然可能分别属于不同的公司,但之间有个不成文的默契。当多艘游轮要靠岸时,一种可能是直接停靠在岸边的码头,另一种方式是靠在已经就位的船旁边。它们可以一艘接着一艘并排起来,离岸较远的船上的游客若要下船,则可以通过其它的船到达岸上。不过有个限制,就是离岸较近的船不可以比离岸较远的船先离开,不然就会被卡住出不去了。

给所有船只的到达和离开时间,问岸边最少需要几个码头,才能让所有的船有办法靠岸。

佔总分30%的测试数据中 n<=15

佔总分100%的测试数据中 n<=1000,并且所有数字皆不超过1000000000。

输入格式

输入的第一行有一个整数n,代表游轮的个数。

接下来有n行每一行分别有两个整数Ai,Bi(Ai<=Bi),代表第i艘游轮的到达和离开时间。

所有船只的到达和离开时间都不会相等。

输出格式

请输出能让所有船只靠岸的最少码头数。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论