I have a matrix. I have a list of people who have to occupy n1,n2,n3 etc cells, different number of cells in different rows. I have to place the people in the cells. Occupying the same cell across rows is considered overlap. Overlap has to be minimized.
I have people referring to this variously as an optimization problem, an allocation problem and even linear programming.
I need to first get a consensus on what is this class of problem called.
Second, I need to know what an efficient solution should look like, in terms of the big-o notation or anything else.
Here is an example:
There is a board of 4 x 4 cells. There are many pieces each of one color (R, G, B). Each color peice has to fill a number of columns in each row. A possible example:
Row1 Row2 Row3 Row4 Red 1 2 3 2 Blue 2 2 0 0 Green 1 0 1 2
That is the input. The input arrangement could be different but it occupies the entire board... no cell is left blank.
The count of same color pieces occupying a COLUMN should be minimized. One possible (bad) arrangement based on the input is this:
1 2 3 4 1 r b b g 2 r r b b 3 r r r g 4 r r g g
This is bad because it actually maximises the count of colors in the same column. A better arrangement is like this:
1 2 3 4 1 r b b g 2 b r r b 3 g r r r 4 r g g r
Overlap is unavoidable, but should be minimized, and provably so. I dont know if there is only one best solution or if there could be many solutions. Even if there could be many solutions, we need to come up with just one.
As I think about it more, it looks like a loose version of eight-queens problem. I am getting worried because I keep seeing recursion and back-tracking.
I am thinking a relaxed version of sudoku puzzle generation.