I have 6 rows of 21 chairs in a building and a booking system where groups of different sizes can book in, with 2 chairs required between each group for social distancing purposes. We want to fit as many people as possible but maintain fairness so smaller groups booking later don't usurp larger groups who already booked earlier. They don't have to be seated in chronological order. Lastly, whilst an attempted booking of more than one person might get rightfully rejected because there's no space to accommodate them, a single booking made after CAN be accepted if they do fit.
I have almost achieved all the above, but not quite... This is how my process works (I could add a lot of code here, but I'm not really after code, rather I need the explanation of what to change that I can't quite grasp. I hope that's ok):
Order the bookings so far chronologically
Loop through each row starting with 21
for each booking, check if the group size + 2 fit. If they do, add them to that rows array, remove them from the bookings array and reduce the number of seats remaining by the group size + 2. Do this until no remaining bookings will fit on this row.
If the remaining seats is 0 then there will be 2 unnecessary 'buffer' seats at the end of the row, but not even a group size of 1 will fit with 2 sets between them and the previous group, so ignore this fact and move on.
If the remaining seats is more than 0 then go through the remaining bookings AGAIN and see if any of the groups will fit WITHOUT adding the 2 seats buffer. If they do, add them to the row array, remove them from the bookings array and break the loop and move onto the next row.
Hopefully you can follow my logic there. It works really well but it isn't filling up the rows in the most efficient way. The bookings don't need to be sat in chronological order but we can't have previous booked in bookings being pushed out by smaller, more recent bookings because they are fitting as efficiently.
Does anyone have any light to shed? My brain is melting!
Since adding small groups is easier than adding large groups, you should place the large groups first.
Suppose the situation is this: you currently have a list of groups that fit. Suddenly, a new group G attempts to book. Try to fit the new group by sorting all the groups by size and placing the groups largest first, smallest last. If this work, accept the new booking of G with the new placement. But if this results in an earlier group no longer fitting, then reject the new group G and keep the old placement.
When you reject a group because you can't fit it, you can also keep the size of that group in memory; the next time a group of equal size or larger attempts to book, you can immediately reject them because you know that you can't fit this size.