問題は以下のように数直線上の問題に言い換えることができます。

$N$ 個の区間 $[s_i,t_i]$ ( ただし $s_i < t_i$ が成立 ) からなる集合 $S$ が与えられる。 $S$ の部分集合 $T$ を作り以下の条件を満たさないようにしたい。

• $T$ から $2$ 要素 $A=[s1,t1],B=[s2,t2]$ を選ぶ方法で $s1 < s2 < t1 < t2$ が成立するものが存在する。

$T$ の要素数としてありうる最大値はいくつか。

前準備としてまず座標を座圧します。次に、各座標ごとにその座標を端点として持つ区間についてもう一方の端点を求めます。
ここで、 $dp[i][j]$ を区間 $[i,j)$ に含まれる区間のみについて問題を解いた場合の答えとします。 ( $i \geq j$ の場合は $0$ とします )
$dp[i][j]$ を求める方法を考えます。まず、 $j-1$ を端点に持つ区間を使わない場合の最大値は $dp[i][j-1]$ です。 $j-1$ を端点に持つ区間を使う場合、もう一方の端点の座標 $p$ は $i \leq p < j-1$ を満たす必要があります。この時の最大値は $dp[i][p]+dp[p+1][j-1]+1$ となります。この $2$ つの値のうち大きいほうが $dp[i][j]$ となります。

上での遷移の考察により、 \(j\) を昇順に \(dp\) を求めていけば各遷移が \(O(1)\) で可能なので \(O(N^2)\) で解くことができました。