D - 足ゲームII Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は以下のようなリズムゲームに挑戦しようとしています。

  • 大きなボタンが N 個ある。このボタンを 1 つ押すには人がちょうど 1 人のる必要があり、他の方法で押すことはできない。
  • 1 人の人が同じ時間に 2 つ以上のボタンを押すことはできない。
  • i 番目のボタンを時刻 S_i から時刻 T_i までの間押し続けると 1 点が得られる。このとき、必ずしも同じ人が最初から最後まで押し続ける必要はなく、途中で押す人を交代しても構わない。
  • ボタンにのったり降りたりするためにかかる時間や、ボタンを押している人を交代するためにかかる時間は無視できるものとする。

高橋君は何人かで協力してこのゲームをプレーすることで N-1 点以上を取りたいと思っています。N-1 点以上を取るために必要な人数の最小値を求めてください。

入力

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

N
S_1 T_1
S_2 T_2
:
S_N T_N
  • 1 行目には、ボタンの個数を表す整数 N (2 ≦ N ≦ 10^5) が与えられる。
  • 2 行目からの N 行には、それぞれのボタンの情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、2 つの整数 S_i, T_i (1 ≦ S_i < T_i ≦ 10^5) が与えられる。これは、i 番目のボタンを時刻 S_i から時刻 T_i までの間押し続けると 1 点が得られることを表す。

出力

N-1 点以上を取るために必要な人数の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

4
1 4
1 2
2 3
3 4

出力例1

1

下図はそれぞれのボタンについて、押し続けると点が得られる時間を表しています。ボタン 1 以外のボタンを 1 人で全て踏むと 3 点を得ることができます。

figure1

入力例2

5
5 11
2 4
3 4
2 7
5 7

出力例2

2

入力例3

4
1 2
1 2015
2015 100000
99999 100000

出力例3

2