This problem can be solved with binary search.

Let \(f(x)\) be the number of sellers who may sell an apple for \(x\) yen; i.e. the number of \(i\)’s such that \(A_i\leq x\).
Let \(f(x)\) be the number of buyers who may buy an apple for \(x\) yen; i.e. the number of \(i\)’s such that \(B_i\geq x\).

What we want to find is the minimum \(x\) such that \(f(x)\geq g(x)\).

Here, \(f(x)\) increases (weakly) monotonically as \(x\) increases, and \(g(x)\) decreases (weakly) monotonically as \(x\) increases.
(The higher the price is, the more sellers and less buyers there are.)

Thus, if \(f(x)\geq g(x)\) for some \(x\), then \(f(y)\geq f(x)\geq g(x)\geq g(y)\) for all \(y\) such that \(x\leq y\). In other words, the predicate \(f(x)\geq g(x)\) has a monotonicity, so the minimum value satisfying it can be found with a binary search.

For a given \(x\), one can compute \(f(x)\) and \(g(x)\) in an \(O(N+M)\) time, so the problem can be solved in a total of \(O((N+M)\log \max A_i)\) time.

Another solution

We can see that only \(A_i\) or \(B_i+1\) can be the answer (proof omitted). Thus, by scanning these values in ascending order, and computing \(f(x)\) and \(g(x)\) based on the difference from the last values, the problem can be solved in a total of \(O((N+M)\log (N+M))\) time, where \(\log\) comes from sorting.