[ZOJ3197]Google Book

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 google.in 输出文件 google.out

【题目描述】

有一本书总共有n页，你可以查询n次，而且它告诉你

每一次可以查询的页码为ai <= i <= bi,即从第ai页到第bi页。问你最少可以查询几次能把这本书所有

的页码都可以查询到。

保證一定存在解。

【输入格式】

the first line is a number N (1<=N<=5000), indicating the number of pages of the book. Then n lines follows. On the i-th line, there will be two integers ai and bi (ai<=i<=bi)

【输出格式】

 a single integer, which is the minimum number of queries to get all the signatures.

【样例输入】 

輸入樣例1:
3
1 1
2 2
3 3
輸入樣例2:
3 
1 1
1 3
3 3

【样例输出】 

輸出樣例1:3
輸出樣例2:1

【提示】

看不懂英语的请面壁1小时。

本题是为了练习NOIP2010《引水入城》一题的第二问。

【来源】

ZOJ Problem Set - 3197 Google Book