\(L_i \leq L_j\) である条件 \(i\) と条件 \(j\) \((i \neq j)\) を同時に満たせないのは、以下の \(2\) つが成り立つときです。

• \(L_i\) と \(L_j\) の偶奇が異なる。
  
• \(L_i < L_j \leq R_i < R_j\) が成り立つ。
  

条件 \(i,j\) が同時に満たせない理由を説明します。
\(X_t\) を \(1\) から \(t\) 文字目までの 「( の個数」 - 「) の個数」 とします。(ただし、 \(X_0 = 0\) とする。)
条件 \(i\) を満たすには \(X_{L_i-1} = X_{R_i}\) かつ、 \(X_{L_i-1} \leq X_t \ (L_i \leq t \leq R_i)\) を満たす必要があります。そのため、\(L_i < L_j \leq R_i < R_j\) が成り立つとき、 \(X_{L_i-1} \leq X_{L_j-1}\) です。
条件 \(j\) を満たす場合も同様に、\(X_{L_j-1} \leq X_{R_i}\) です。
ここで、条件 \(i,j\) を同時に満たすとすると、\(X_{L_i-1} \leq X_{L_j-1} \leq X_{R_i}\) かつ \(X_{L_i-1} = X_{R_i}\) より、 \(X_{L_i-1} = X_{L_j-1}\) となるが、これは \(L_i,L_j\) の偶奇が異なることに矛盾します。

逆に、上の \(2\) つが成り立たないような条件は同時に満たすことが可能です。
具体的には以下のアルゴリズムで条件を満たす \(S\) を構築できます。

\(t = 1,2,...,N\) 文字目を以下のように定める。

• \(t = L_i\) となる \(i\) があれば、 \(S_t=\) ( とする。
• \(t = R_i\) となる \(i\) があれば、 \(S_t=\) ) とする。
• それ以外のとき、直前の文字が ( なら ) に、) なら ( にする。

これらの条件の関係をグラフに対応させて考えます。
条件 \(i\) に対応する頂点 \(i\) を考え、条件を同時に満たすことができないような頂点の組 \(i,j\) の間に辺を繋ぎます。
すると、どの \(2\) 頂点も辺で繋がらないように、頂点をできるだけ多く選ぶ問題となります。これは最大安定集合問題です。
また、辺は \(L_i, L_j\) の偶奇が異なる \(i,j\) の間にのみ繋がれるため、グラフ全体は二部グラフになります。
よってこの問題は二部グラフの最大安定集合問題になりました。これは二部グラフの最大マッチングを求めることにより解くことができます。
グラフの頂点数は \(O(M)\), 辺の数は \(O(M^2)\) であるため、Dinic 法により \(O(M^{2.5})\) で解くことが出来ます。