001 - イベントが見たい！

問題

T 君はとてもイベント好きです。

見に行きたいイベントが $N$ 個あります。これらは時間 $S_i$ から始まり、時間 $T_i$ に終わります。

イベントは必ず始まりから終わりまですべて見るものとして、できるだけ多くのイベントに参加したいです。

イベントを重複して見ることはできません。開始の瞬間・終了の瞬間も重なってはいけません。

T 君は何個のイベントを見ることが出来るでしょうか。

入力

$1$ 行目にイベント数 $N$ が与えられる。

$2$ ~ $1$ + $N$ 行目まで、各イベントの開始時刻、終了時刻の $S_i$ , $T_i$ が与えられる。

$N$
$S_1$ $T_1$
$S_2$ $T_2$
    .
    .
    .
$S_N$ $T_N$

出力

T 君が見られるイベントの数の最大値を出力せよ。

制約

• $1 \leq N \leq 10^5$
• $1 \leq S_i \leq T_i \leq 10^9$

入出力例

入力例1

3
1 3
3 5
5 7

出力例1

2

解説

イベントはこの図のような時間配分になっている。

イベント $1$　, イベント $3$ に参加すれば $2$ つ参加でき、これが最大となるので $2$ を出力する。

コメント

結構見落としがちな基本問題ですので、解けるようにしておきましょう。

2018 7/2 0:22 ソースコードを公開しました