この問題は二分探索を用いて解くことができます。

\(f(x)\) を、りんごを \(x\) 円で売ってもよいと考える売り手の人数、すなわち \(A_i\leq x\) を満たす \(i\) の個数とします。
\(g(x)\) を、りんごを \(x\) 円で買ってもよいと考える買い手の人数、すなわち \(B_i\geq x\) を満たす \(i\) の個数とします。

求めるものは \(f(x)\geq g(x)\) を満たす最小の \(x\) です。

ここで、\(f(x)\) は \(x\) の増加に伴い(広義)単調増加し、\(g(x)\) は \(x\) の増加に伴い(広義)単調減少します。
（値段を釣り上げると売り手は増え買い手は減ります）

したがって、ある \(x\) で \(f(x)\geq g(x)\) となるなら、\(x\leq y\) となる任意の \(y\) で \(f(y)\geq f(x)\geq g(x)\geq g(y)\) を満たします。すなわち、\(f(x)\geq g(x)\) であるかどうかには単調性があるため、これを満たす最小の値は二分探索により求めることができます。

与えられた \(x\) に対して \(f(x),g(x)\) の値を求めるには \(O(N+M)\) 時間かかるので、問題は \(O((N+M)\log \max A_i)\) で解けます。

別解

答えとなりうるのは、\(A_i\) の値か \(B_i+1\) の値に限ることがわかります（証明略）。したがって、これらの値を小さい順に調べ、\(f(x),g(x)\) の計算の際には前の値との差分のみを調べることで、全体で \(O((N+M)\log (N+M))\) で問題を解くことができます。\(\log\) はソートによるものです。