\(A=(a_1,a_2, \ldots,a_N), B=(a_{N+1}, \ldots, a_{2N})\) とします。

\(\min(A)\) を \(\mathrm{X}\) とします。

\(A_i=\mathrm{X}, A_i \geq B_i\) なる \(i\) が存在するなら、そのような \(i\) のうち、\(B_i\) 最小のものを選ぶことで辞書順最小の数列を得ることができます。

以降、\(A_i = \mathrm{X}\) のとき \(A_i \leq B_i\) を仮定します。このとき、\(A_i = \mathrm{X}\) であるような \(i\) は全て選ぶのが最適であることが示せます(そうでないような選び方は明らかに辞書順で大きくなります)。

\(A_i = \mathrm{X}\) を満たす \(i\) を昇順に並べた数列を \(y=(y_1, y_2, \ldots, y_K)\) とします。\(y_K <j \leq N, A_j \leq B_{c_1}\) を満たす \(j\) たちをどのように選ぶのが最適か考えましょう。

\((A_j,j)\) で昇順に並べた順で見たときに、\(A_j < B_{y_1}\) である要素については \(j\) が \(y\) の末尾の要素よりも大きいならば \(y\) の末尾に追加するという選び方が最適であることが示せます(そうでないような選び方は辞書順で大きくなります)。

最後に考えるべきは \(A_j = B_{y_1}\) であるような \(j\) を選ぶべきかどうかです。これは、そのような \(j\) を \(1\) つ追加したときに辞書順で小さくなるならば可能な限り選ぶべきで、そうでなければ \(1\) つも選ばないのが最適であることが示せます。

適切に実装すれば時間計算量 \(O(N)\) で答えを求めることができますが、時間計算量 \(O(N \log N)\) のアルゴリズムでも十分高速に動作します。