Let ~s_1, \dots, s_n~ be the input sequence of bins and ~s_i \le m~ for ~i = 1, \dots, n~. The ~k~ leftmost bins can be put into the next ~k~ bins in some order if and only if ~2k \le n~ and there exists a permutation ~p~ of the numbers ~1, \dots, k~, such that

$$\displaystyle s_i < s_{k+p(i)}\text{ for }i = 1, \dots, k \quad (1)$$

The solution to the problem is the largest ~k~ satisfying condition (1). Assume that ~k~ is a solution and ~p~ is a permutation satisfying condition (1). Let

• ~x = \max(s_1, \dots, s_k)~ and ~x = s_i~
• ~y = \max(s_{k+1}, \dots, s_{k+k})~ and ~y = s_{k+j}~

It is obvious that ~x < y~. Assume that ~p(i) = k+jj~ and ~p(ii) = k+j~. Then

$$\displaystyle s_i < s_{k+jj} \le s_{k+j}$$ $$\displaystyle s_{ii} \le s_i < s_{k+jj}$$

Therefore we can modify the permutation ~p~ such that ~p(i) = j~ and ~p(ii) = jj~, and the modified ~p~ also satisfies condition (1). Let ~L(x)~ be the number of bins of size ~x~ in the first ~k~ bins, and ~R(x)~ be the number of bins of size ~x~ in the next ~k~ bins, that is

$$\displaystyle \begin{align*} L(x) &= |\{i : 1 \le i \le k, s_i = x\}| & x = 1, \dots, m \\ R(x) &= |\{j : k+1 \le j \le 2k, s_j = x\}| & x = 1, \dots, m \end{align*}$$

Define ~R(m+1) = 0~ and ~D(m+1) = 0~ and

$$\displaystyle D(x) = D(x+1)+R(x+1)-L(x) \quad x = m, \dots, 1$$

Now we can state that the ~k~ leftmost bins can be put into the next ~k~ bins in some order if and only if condition (2) holds.

$$\displaystyle D(x) \ge 0 \quad x = m, \dots, 1 \quad (2)$$

Values of ~L(x)~ and ~R(x)~ can be computed in ~\Theta(n)~ running time and then checking for the condition (2) takes ~\mathcal O(m)~ time. Therefore for a given value of ~k~ we can check whether ~k~ is a solution in ~\mathcal O(mn)~ time. Moreover, if we already computed the values of ~L~ and ~R~ for a given ~k~ then for ~k-1~ we have to modify ~L(k)~, ~R(k)~, ~R(2k)~ and ~R(2k-1)~ only. As a consequence, we obtain an ~\mathcal O(mn)~ worst case running time algorithm. The required memory is ~\Theta(m+n)~.

We can speed up a bit by recomputing only those ~D(x)~ that might be changed by decreasing the value of ~k~.