We are given $ 2n – 1$ boxes with black and white balls. In the $ i$ -th, box there are $ w_i$ white and $ b_i$ black balls. It is required to choose $ n$ boxes so that, the sum of the white balls is at least $ W/2$ , and the sum of black balls is at least $ B/2$ . Solve for $ O(n\log{n})$ .

What I am currently thinking is this:

Generate some hashtable to be able to track the boxes that we chose.

Sort the boxes by the quantity of the white (in increasing order) balls and chose the last $ n$ balls every time keeping them in our hashtable.

Sort by the quantity of the black balls and do the same. Check every time to see if we already chose the box or not. Here comes the problem: Suppose we didn’t. Then we can face a situation where we already have $ n$ boxes that have in total at least $ W/2$ white balls but at the same time, they have in total less than $ B/2$ black balls. How can we overcome this problem?

We can’t just switch the chosen boxes that have the least number of white balls with the one that have the maximum available number of black balls since the box with white balls can contain significant amount of black balls on its own.