This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions. (If this is the wrong SE to ask this question, rather than downvoting it, could you comment what the correct SE is, and I can post it there)
Scenario 1: Tough (for me!) There is a one day conference with a set of (4 or more) sessions. The conference will be attended by a number of companies, each one being represented by a (1 or more) representatives.
Across sessions the number of representatives for each company will vary (and may be zero), with each individual having the same chance of being present as any other individual (so there is an increasing likelihood of a company being represented when it has more representatives).
There is a single row of seats in the conference. There are more than enough seats for the most popular session. (e.g., if the most popular session has 100 delegates, there could be 120 seats for the whole conference).
Constraints & Priorities (from highest to lowest)
- Constraint: Company representatives must be seated
- Constraint: Company representatives sit next to each other
- Constraint: seats will not be greater than 125% most popular session.
- Priority: A company representative should not need to change seat across consecutive sessions
- Priority: Companies should be in approximately alphabetical order.
Goal To fit the constraints and priorities optimally. Example. 15 chairs, 4 companies (A-D), 4 sessions (S1-S4).
// Session attendees by company S1: A2 B6 C3 D3 S2: A4 B5 C1 D2 S3: A3 B3 C4 D1 S4: A5 B2 C5 D0 // Possible solution (I did this manually!) S1: [AA.BBBBBBCCCDDD] S2: [AAAABBBBBC...DD] S3: [AAA...BBBCCCC.D] S4: [AAAAA..BBCCCCC.]
Question How can I solve this algorithmically? The algorithm doesn’t have to be particularly fast but it does need to yield working results.
Scenario 2: Tougher?! The same as above but the row of seats has enforced break points (like pillars, walkways, etc). I think this latter issue is merely a ‘knapsack’-type modification to the above problem
Thoughts towards a solution It seems that it should be possible to have consecutive seating available in most cases, which implies that a solution could be found by identifying company-invariant seats by filling the minimum company representation across all sessions, leaving gaps between companies that are somehow calculated based on the variation of the company and it’s neighbour.
It is trivial to find cases where there is only a partial solution, eg the following, but that’s okay. I still need to get the best solution I can.
S1: [AAAABC] S2: [ABCCCC]