B. 安全系统(safe)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

蒜国有一条延绵不绝的铁路,铁轨可抽象成一个数轴。 为了保护铁轨,蒜国建立了一套严密的安全系统。 这个系统由一系列的安全区间组成,每个安全区间由两个整数表示,表示其在数轴上的起始位置和终止位置。

在维护安全系统的过程中,需要知道数轴上哪个点被安全区间覆盖的次数最多。这样,相关部门就能够更有针对性地加强保护措施,确保铁轨的整体安全。

为了解决这一问题, 你需要设计一个算法,给定n个安全区间,找出数轴上被区间覆盖最多次的点,回答该点被覆盖的次数。

输入格式

第一行一个整数n,表示安全区间的个数。

接下来n行,每行两个整数x和y, 表示一个安全区间在数轴上的起始位置和终止位置。

输出格式

输出一行个整数,表示最大覆盖次数。

样例

样例输入1

4
2 6
8 9
1 5
1 2

样例输出1

3

解释:

数据范围与提示

对于50%的数据,1≤n≤1000,1≤x≤y≤1000。

对于80%的数据,1≤n≤10^5,1≤x≤y≤10^8

对于100%的数据,1 ≤ n ≤ 10^5,1≤x≤y≤10^20