Let us first consider, when we fix a size \(x\) of the box to newly purchase, how we can determine if step 2 is feasible.

In conclusion, the following proposition can be used:

Sort \(A\) in ascending order to obtain \(a=(a_1,a_2,\dots,a_N)\). Insert \(x\) to \(B\) and sort it in ascending order to obtain \(b=(b_1,b_2,\dots,b_N)\). Then Step \(2\) is feasible if and only if \(a_i \leq b_i\) for all \(i\ (1\leq i\leq N)\).

Proof

The sufficiency is obvious, so we will show the necessity: “if step 2 is feasible, then \(a_i \leq b_i\) for all \(i\ (1\leq i\leq N)\).”

Renumber the toys and boxes, so that the toy corresponding to \(a_i\) is called toy \(i\), and the box for \(b_i\) as box \(i\). When step 2 is feasible, there exists a permutation \(p=(p_1,p_2,\dots,p_N)\) of \((1,2\dots,N)\) such that “\(a_i \leq b_{p_i}\) for all \(i\ (1\leq i\leq N)\)” ().

Assume that there exists \(i\ (1\leq i < N)\) with \(p_i > p_{i+1}\). Then we have \(a_i\leq a_{i+1}\leq b_{p_{i+1}}\leq b_{p_i}\), thus \(a_i\leq b_{p_{i+1}}\) and \(a_{i+1}\leq b_{p_i}\); then () still holds after swapping \(p_i\) and \(p_{i+1}\). By repeating this operation while \(i\ (1\leq i < N)\) with \(p_i > p_{i+1}\) exists, one can make \(p=(1,2,\dots,N)\) while maintaining (). When \(p=(1,2,\dots,N)\), () means \(a_i \leq b_i\) for all \(i\ (1\leq i\leq N)\), which is what we want (end of proof).

Therefore, this criteria allows us to use binary search to find the minimum \(x\) that satisfies the condition. If you sort the sequence \(a\) and \(b\) for every decision, it costs a total of \(O(N\log (\max A_i)\log N)\) time, which does finish within the execution time limit; one can also tweak it to optimize it to \(O(N\log (\max A_i))\).

One can also solve this problem without binary search, by the greedy algorithm below instead. (The validity follows from the discussion for a fixed \(x\) above.) The complexity is \(O(N\log N)\), where sorting is the bottleneck.

1. Let toy \(i\) and box \(j\) be the largest remaining toy and box, respectively.
2. If \(A_i\leq B_j\): it is optimal to place toy \(i\) into box \(j\). Remove toy \(i\) from the toy set and box \(j\) from the box set; go back to step 1.
3. If \(A_i> B_j\): you cannot place toy \(i\) to any of the remaining boxes, so you need to buy a new box of size at least \(A_i\). Buying a box of size exceeding \(A_i\) is useless, so set \(x=A_i\) to apply the criteria above. If it is met, the answer is \(A_i\); otherwise it is \(-1\).

Inspecting the behavior of this greedy algorithm, one can come up with an even simpler algorithm as follows. The complexity remains \(O(N\log N)\).

1. Sort \(A\) and \(B\) in ascending order.
2. If there exists \(i\ (1\leq i\leq N-1)\) with \(A_i > B_i\): the answer is \(-1\).
3. Otherwise: the answer is \(A_{i'+1}\), where \(i'\) is the maximum \(i\ (1\leq i\leq N-1)\) with \(A_{i+1} > B_i\) (or \(0\) if nothing applies).

Sample code (C++, binary search, \(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;
}

Sample code (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;
}