[ABC014C] AtColor

题面翻译

题意翻译

给出n个区间，求出被覆盖次数最多的区间的覆盖次数

题目描述

AtColor社は，$0$ から $1,000,000$ まで $1,000,001$ 通りの濃さがある灰色の絵の具を販売することにしました．$0$ が最も黒く，$1,000,000$ が最も白い絵の具です．

しかし，途方も無い数の濃さのバリエーションがある一方，消費者には細かい違いが分からないということが判明しました．これを知ったAtColor社は，売れない濃さの絵の具を生産するのはやめて，最も人気のある濃さの色の絵の具1つだけを販売することにしました．

AtColor社は上記を達成するために，最も人気な絵の具がどのくらい売れるかをアンケート調査で調べることにしました． AtColor社がどの範囲の濃さの絵の具なら購入したいかというアンケートを消費者に対して行ったところ， 「$a\ ≦\ x\ ≦\ b$ を満たす濃さ $x$ の絵の具ならば購入する」という形式の情報が $n$ 件得られました．

あなたの仕事は，これらの情報から，最も多くの消費者に購入される濃さの絵の具について，その絵の具を購入する消費者の数を出力するプログラムを作ることです．

输入格式

入力は以下の形式で標準入力から与えられる．

$n$ $a_{1}\ b_{1}$ $a_{2}\ b_{2}$ : $a_{n}\ b_{n}$

• $1$ 行目には，アンケート情報の数 $n\ (1\ ≦\ n\ ≦\ 100,000)$ が与えられる．
• 続く $2$ 行目から $n$行は，各アンケート情報を表す． $a_i,b_i(0≦a_i≦b_i≦1,000,000)$ はそれぞれ $i$ 番目のアンケート情報における濃さの下限と上限(端を含む)を表す整数で，空白区切りで与えられる．

输出格式

最も多くの消費者に購入される濃さの絵の具について，それを購入する消費者の数を $1$ 行に出力せよ．出力の末尾に改行を入れること．

样例 #1

样例输入 #1

4
0 2
2 3
2 4
5 6

样例输出 #1

3

样例 #2

样例输入 #2

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

样例输出 #2

4

提示

部分点

この問題には2つのデータセットがあり，データセット毎に部分点が設定されている．

• $1≦n≦2,000$ を満たすデータセット 1 に正解した場合は $30$ 点が与えられる．
• 追加制約のないデータセット 2 に正解した場合は，上記のデータセットとは別に $70$ 点が与えられる．

Sample Explanation 1

- 濃さ $0,1,4,5,6$ の絵の具は，1人の消費者によって購入してもらえます． - 濃さ $2$ の絵の具は，3人の消費者によって購入してもらえます． - 濃さ $3$ の絵の具は，2人の消費者によって購入してもらえます． - 他の濃さの絵の具は誰にも購入してもらえません． よって，$3$ を出力します．