A Seating Optimisation Problem Suppose that you have a cinema hall of size $n\times m$ (where $n$ is the number of rows and $m$ the number of seats in a row). Now, given that there are exactly $l$ people who need only the left armrest, $r$ who need the right, $b$ who need both, and $z$ who need none, we need to find out the maximum number of people we can fit into the cinema hall.
I tried to split it into cases - I could figure out that if $l+r+z$ is greater than $n\times m$, then the entire cinema hall can be filled. But I'm not able to figure out how to accommodate the people who need both the armrests.
 A: This is an assignment problem that can be modeled as a min cost flow problem:
Create a bipartite graph $G=(V_1\cup V_2,E)$, where


*

*$V_1$ is the vertex set representing all $l+r+b+z$ people wanting to sit,

*$V_2$ is the vertex set representing all $m\;n$ seats.

*$E$ is the edge set built as follows:


Create an arc from all $z$ type vertices of $V_1$ to all vertices of $V_2$, with a $0\$$ cost.
Create an arc from all $l$ type vertices of $V_1$ to all vertices $u$ of $V_2$, with the following cost structure: if $u$ is a seat on the right edge, add a $0\$$ cost, if it is a middle one, add a $1\$$ cost, and if it is a seat on the left edge, add a $2\$$ cost.
Create an arc from all $r$ type vertices of $V_1$ to all vertices $u$ of $V_2$, with the following cost structure: if $u$ is a seat on the right edge, add a $2\$$ cost, if it is a middle one, add a $1\$$ cost, and if it is a seat on the left edge, add a $0\$$ cost.
Create an arc from all $b$ type vertices of $V_1$ to all vertices $u$ of $V_2$, with the following cost structure: if $u$ is a seat on the right edge, add a $1\$$ cost, if it is a middle one, add a $0\$$ cost, and if it is a seat on the left edge, add a $1\$$ cost. 
All arcs have unit capacities.
Computing a maximum flow with minimum cost on this network will give an assignment with as many people as possible. The cost structure is such that the algorithm will try to fit in priority the $l$ people on the right edge, the $r$ people on the left edge, and the $b$ people in the middle. Obviously, it will give priority to the $z$ type people, then to the $r$ and $l$, then to the $b$.
A: I will assume each row of $m$ seats has $m+1$ armrests, so that each seat has an armrest on each side.  
A lot depends on whether $m+1$ is even or odd.  If it's odd, start by seating one R-type person at the far right of each row, which will leave those rows with an even number of unused armrests (and an odd number of open seats).  If you run out of R-types before you've run out of rows, continue with L-type people at the far left of the remaining rows.  If you run out of L-types and still have rows with an odd number of armrests, go ahead and use some Z-type people (if there are any) as if they were L-types.  If you still wind up with rows with an odd number of armrests, you might as well remove a seat (and armrest) from one end of those rows, because it's not going to be of any help to have it.
So now each row has an even number of available armrests.  If you have any leftover R- or L-type people, bring them in two at a time and seat them at the far right (for R-types) and/or far left (for L-types) of some row.  Note that doing so always leaves each row with an even number of armrests for an odd-numbered stretch of seats.  If this procedure doesn't all by itself fill all the seats, you will have at most a single R- or L-type person left over (if the total number of such people was odd); you might as well reclassify that person as of B-type.
Now start seating B-type people, putting each B-type say as far to the right in a row as possible.  Again, doing so always leaves each row with an even number of available armrests, so you'll be able to continue seating B-types until the total number (for all rows) drops to $0$ (unless you run out of B-types first).  If there are still some B-types hoping to be seated, they're out of luck -- the armrests are all taken.
Finally, bring in the Z-types (if any) and let them sit between the B-types.  You'll either fill the auditorium or you'll run out of Z-types.  In either case you've seated as many people as possible.
