アルゴリズムとデータ構造

交差しない区間の最大数

整数 n 個の区間 [l; r] (両端を含む) が与えられたとき、互いに交差しない区間を最大でいくつ選び出せるかを求めます。
なお、端点が同じ座標の区間同士は交差しないものとみなします。

入力

最初の行に区間の数を表す整数 n (1 ≤ n ≤ ) が与えられます。
続く n 行には、空白区切りの 2 つの整数 と ( ) が与えられ、これらは区間の左端と右端を示しています。

出力

交差しない区間の最大個数を出力してください。

例

入力
出力
3 3 5 2 4 4 8
2
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue