問題
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 ソースコードを公開しました