B - 区間スケジューリング問題 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 個のタスクがあります。i 個目のタスクは A_{i} 日目の朝に始まり、B_{i} 日目の夜に終わります。その間の日は全てそのタスクに専念する必要があります。

あなたはこれらのタスクを自由に選んで実行することができます。ただし、同じ日に複数のタスクを行うことはできません。実行可能なタスクの個数の最大値を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_{i} \leq B_{i} \leq 10^9
  • 入力はすべて整数である。

入力

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

N
A_{1} B_{1}
A_{2} B_{2}
:
A_{N} B_{N}

出力

実行可能なタスクの個数の最大値を出力せよ。

入力例 1

3
1 5
4 6
6 8

出力例 1

2

1 番目と3 番目のタスクを実行することができます。3 つのタスクを全て行うことはできないので、2 が最大値となります。