まずは、新しく購入する箱の大きさ \(x\) を \(1\) つ決めた際に、操作 \(2\) を行えるかどうかを判定する方法について考えます。

結論としては、これは以下の命題を用いて判定できます。

\(A\) を昇順にソートして得られる列を \(a=(a_1,a_2,\dots,a_N)\)、 \(B\) に \(x\) を追加した上で昇順にソートして得られる列を \(b=(b_1,b_2,\dots,b_N)\) とおく。このとき、操作 \(2\) を実行できる必要十分条件は、すべての \(i\ (1\leq i\leq N)\) について \(a_i \leq b_i\) が成り立つことである。

証明

十分性は明らかなので、必要性、すなわち「操作 \(2\) を実行できるならば、すべての \(i\ (1\leq i\leq N)\) について \(a_i \leq b_i\)」を示せばよい。

\(a_i\) に対応するおもちゃをおもちゃ \(i\)、\(b_i\) に対応する箱を箱 \(i\) と改めて呼び直すことにする。操作 \(2\) を実行できることから、ある \((1,2\dots,N)\) の順列 \(p=(p_1,p_2,\dots,p_N)\) が存在して、「すべての \(i\ (1\leq i\leq N)\) について \(a_i \leq b_{p_i}\)」(＊) が成り立つ。

\(p_i > p_{i+1}\) なる \(i\ (1\leq i < N)\) が存在すると仮定する。このとき、\(a_i\leq a_{i+1}\leq b_{p_{i+1}}\leq b_{p_i}\) より特に \(a_i\leq b_{p_{i+1}}\) かつ \(a_{i+1}\leq b_{p_i}\) であるから、\(p_i\) と \(p_{i+1}\) を入れ替えても (＊) が成立する。この操作を \(p_i > p_{i+1}\) なる \(i\ (1\leq i < N)\) が存在する限り繰り返せば、(＊) を成立させたまま \(p=(1,2,\dots,N)\) にできる。 \(p=(1,2,\dots,N)\) のときの (＊) は「すべての \(i\ (1\leq i\leq N)\) について \(a_i \leq b_i\)」であり、これは示したかったものである（証明終）。

よって、この判定法を用いれば、条件を満たす \(x\) の最小値を 二分探索 で求めることができます。判定のたびに列 \(a,b\) をソートで求めると \(O(N\log (\max A_i)\log N)\) になり、これでも実行時間制限に間に合いますし、少し工夫をすれば \(O(N\log (\max A_i))\) にすることもできます。

また、二分探索を使わずに、以下のような貪欲法でこの問題を解くこともできます。（正当性は上記の \(x\) を固定した際の判定方法から示せます。）計算量はソートがボトルネックとなって \(O(N\log N)\) です。

1. 今ある中で最も大きいおもちゃをおもちゃ \(i\)、最も大きい箱を箱 \(j\) とおく。
2. \(A_i\leq B_j\) である場合：おもちゃ \(i\) を箱 \(j\) に入れるのが最適である。おもちゃの集合からおもちゃ \(i\) を除き、箱の集合から箱 \(j\) を除いた上で、ステップ 1. に戻る。
3. \(A_i> B_j\) である場合：今あるどの箱にもおもちゃ \(i\) を入れることができないので、大きさ \(A_i\) 以上の箱を新しく購入する必要がある。大きさが \(A_i\) より大きい箱を買うメリットはないので、\(x=A_i\) とした上で上記の判定法を適用し、条件を満たすならば答えは \(A_i\)、満たさないならば \(-1\) である。

なお、この貪欲法の動作を観察すれば、以下のような簡単な方法で答えを求められることもわかります。計算量は変わらず \(O(N\log N)\) です。

1. \(A,B\) それぞれを昇順にソートする。
2. \(A_i > B_i\) なる \(i\ (1\leq i\leq N-1)\) が存在する場合：答えは \(-1\)。
3. そうでない場合：\(A_{i+1} > B_i\) なる最大の \(i\ (1\leq i\leq N-1)\)（存在しなければ \(0\)） を \(i'\) として、答えは \(A_{i'+1}\)。

実装例 (C++、二分探索、\(O(N\log (\max A_i)\log N)\)) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n - 1);
    for (int &i: a) cin >> i;
    for (int &i: b) cin >> i;
    sort(a.begin(), a.end());
    int ok = 1 << 30, ng = 0;
    auto f = [&](int x) -> bool {
        vector<int> nb = b;
        nb.push_back(x);
        sort(nb.begin(), nb.end());
        for (int i = 0; i < n; i++) {
            if (a[i] > nb[i]) return false;
        }
        return true;
    };
    if(!f(ok)) {
        cout << -1 << endl;
        return 0;
    }
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        if (f(mid)) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

実装例 (C++、\(O(N\log N)\)) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n - 1);
    for (int &i: a) cin >> i;
    for (int &i: b) cin >> i;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > b[i]) {
            cout << -1 << endl;
            return 0;
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        if (a[i + 1] > b[i]) {
            cout << a[i + 1] << endl;
            return 0;
        }
    }
    cout << a[0] << endl;
}