Hello all, the problem at hand is as follows: given an array (list) of strings, break up that list into 2 lists having an equal number of items (or as close to equal as possible). Not as easy as it sounds.
The original list in question basically is a list of sentences. If each sentence occupied one list element, there would be no problem: I have a list of 10 lines, divide by 2, and I have my two lists of 5 lines each. But not so fast! The original list my contain sentences that may occupy one, two, or three lines - and when the list is split into two, a rule is that we cannot break up a multi-line sentence.
Here is an example of an initial list (the beginning of each sentence starts with "* "):
(0) * This is a short one.
(1) * Another short one.
(2) * Still another.
(3) * Yet another.
(4) * This is a very long one
(5) spanning a whopping
(6) three lines.
(7) * Back to a short one.
(8) * And another short one.
(9) * Last one here.

So if we keep the original order and split the list at the midpoint, the result is less than desirable. We would get:
LIST 1:
(0) * This is a short one.
(1) * Another short one.
(2) * Still another.
(3) * Yet another.
(4) * This is a very long one
(5) spanning a whopping
(6) three lines.
LIST 2:
(0) * Back to a short one.
(1) * And another short one.
(2) * Last one here.
--- OR ---
LIST 1:
(0) * This is a short one.
(1) * Another short one.
(2) * Still another.
(3) * Yet another.
LIST 2:
(0) * This is a very long one
(1) spanning a whopping
(2) three lines.
(3) * Back to a short one.
(4) * And another short one.
(5) * Last one here.

Although a multi-line sentence is not permitted to broken up (i.e. the long one cannot start at the bottom of LIST 1 and finish at the top of LIST 2), we are permitted to reorder the original list, such that when we split it we get an even number of lines (or as close to even as we can get) per the two lists.
I am looking for an algorithm that figure out how to reorder the original list to accomplish this goal. For example, an algorithm that could determine a reordering of the list as follows:
(0) * Still another.
(1) * Yet another.
(2) * This is a very long one
(3) spanning a whopping
(4) three lines.
(5) * This is a short one.
(6) * Another short one.
(7) * Back to a short one.
(8) * And another short one.
(9) * Last one here.
Which, when split into 2 lists, would give us 5 elements per list:
LIST 1:
(0) * Still another.
(1) * Yet another.
(2) * This is a very long one
(3) spanning a whopping
(4) three lines.
LIST 2:
(0) * This is a short one.
(1) * Another short one.
(2) * Back to a short one.
(3) * And another short one.
(4) * Last one here.

Help is appreciated ...