各開きカッコに対応する \(N\) 個の頂点と各閉じカッコに対応する \(N\) 個の頂点からなるグラフを考えます。 \(x_{1, i} < x_{2, j}\) かつ \(y_{1, i} < y_{2, j}\) となる開きカッコ \(i\) と閉じカッコ \(j\) に対応する頂点に辺を張ります。

\(N\) 個の長方形を平面に配置することができるには、このグラフにおいて完全マッチングが存在する必要があります。完全マッチングが存在しない場合、答えは No となります。

任意の異なる \(2\) つの長方形の共通部分が、面積が \(0\) となるか、または一方の長方形に一致するよう \(N\) 個の長方形を平面に配置できるという条件（以下、条件とする）を満たすように長方形を配置できるかは 構成する完全マッチングに依存します。

ここで、以下の貪欲アルゴリズムは最大マッチングを構成します。また、この貪欲アルゴリズムが完全マッチングを構成するならば、それが条件を満たす唯一の完全マッチングです。

閉じカッコを \(x\) の昇順、 \(x\) 座標が同じならば \(y\) の昇順に見て、マッチングできる開きカッコがあるならば \(y\) 座標最大、\(y\) 座標が同じものなら \(x\) 座標最大のものとマッチングさせる

唯一の完全マッチングであることの証明

上記のアルゴリズムで構成された完全マッチング \(M_1\) 以外に、条件を満たす \(N\) 個の長方形を平面に配置できる完全マッチング \(M_2\) があると仮定します。

そのとき以下を満たす開きカッコ \(i\) が存在します。

マッチング \(M_1\) において \(i\) とマッチする閉じカッコを \(j_1\), マッチング \(M_2\) において \(i\) とマッチする閉じカッコを \(j_2\) とすると \(j_1 \neq j_2\) であり \(x_{2, j_1} \leq x_{2, j_2}\) または \(y_{2, j_1} \leq y_{2, j_2}\) である

すると、閉じカッコ \(j_1\) とマッチする開きカッコは \(i\) と \(j_2\) によってできる長方形の外部にあります。これは、 \(M_2\) が条件を満たす \(N\) 個の長方形を平面に配置できる完全マッチングであることに矛盾します。

よって 条件を満たす \(N\) 個の長方形を平面に配置できる完全マッチングは上記のアルゴリズムで構成される完全マッチングのみであることが証明されました。

まず、貪欲アルゴリズムで最大マッチングを構成しその最大マッチングが完全マッチングであるか判定します。完全マッチングであるならば、その完全マッチングが条件を満たすかどうか判定し満たすならば Yes 、満たさないならば No とすればよいです。

貪欲アルゴリズムは std::set などを用いることで \(O(N\log N)\) でできます。条件を満たすかの判定は std::set やstd::multisetを用いるか、セグメントツリーを用いることで \(O(N\log N)\) でできます。よって全体で \(O(N\log N)\) でこの問題が解けました。

実装例 1 判定にstd::multisetを用いています。

実装例 2 判定にセグメントツリーを用いています。