问题 E: 5.迎江寺

问题 E: 5.迎江寺

题目描述

  刚迎来了2014年元旦,又将逢春节,每次大年初一小明都要和爸爸妈妈到迎江寺去烧香拜佛,祝愿新的一年里心想事成。
记得每年都人山人海,非常热闹。进进出出的人实在太多了,寺里的住持想知道,在某一时刻,寺里的游客的最多人数,以便来年改进措施解决人满为患的状况,如超过一定人数,就要实行限流。大年初一共有n位游客入寺,第i位入寺游客,入寺时间为ai,在第bi时刻离开寺庙,因此第i位游客在寺内中的时间是[ai,bi],即ai≤t≤bi中所有可能的t,请写一个程序,读入ai与bi,1≤i≤n,找出同一时刻最多会有多少游客在寺中。
住持想知道最多有多少游客在同一时刻都在寺内,但游客们进进出出寺庙的记载实在很乱,于是住持请聪明的你编程帮忙统计。

输入

输入文件temple.in中
第一行只有一个整数n,表示共有n个游客进出寺庙的记载。
接下来n行,每行二个整数a和b,表示有一个游客在第a时刻进入寺庙,他在第b时刻后离开寺庙。

输出

输出文件temple.out中仅有一行,该行只有一个整数,表示最多有多少游客在同一时刻都在寺庙里面。

样例输入输出

输入#1 复制
4
2 6
8 9
1 5
1 2
输出#1 复制
3

提示

【样例说明】

第一个游客在时刻2进入寺庙里面,在时刻6后离开寺庙;第二个游客在时刻8进入寺庙里面,在时刻9后离开寺庙;第三个游客在时刻1进入寺庙里面,在时刻5后离开寺庙;第四个游客在时刻1进入寺庙里面,在时刻2后离开寺庙;
因此在时刻2时,最多有3个游客(第一个、第三个和第四个)在寺庙里面。
【数据规模】
50%的数据中,1≤n≤1000;每个游客进出寺庙的时刻a和b满足:1≤a≤b≤3000;
100%的数据中,1≤n≤100000,1≤a≤b≤100000000。

序号 标题 作者 发表时间 费用 订购数 操作