蒜国有一条延绵不绝的铁路,铁轨可抽象成一个数轴。 为了保护铁轨,蒜国建立了一套严密的安全系统。 这个系统由一系列的安全区间组成,每个安全区间由两个整数表示,表示其在数轴上的起始位置和终止位置。
在维护安全系统的过程中,需要知道数轴上哪个点被安全区间覆盖的次数最多。这样,相关部门就能够更有针对性地加强保护措施,确保铁轨的整体安全。
为了解决这一问题, 你需要设计一个算法,给定n个安全区间,找出数轴上被区间覆盖最多次的点,回答该点被覆盖的次数。
第一行一个整数n,表示安全区间的个数。
接下来n行,每行两个整数x和y, 表示一个安全区间在数轴上的起始位置和终止位置。
输出一行个整数,表示最大覆盖次数。
4 2 6 8 9 1 5 1 2
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