I thought of this problem randomly and have done no research or any thinking on it, I was just wondering if it sounded similar to any existing problem.
The dining hall at my college is an all you can eat buffet. Usually you can just walk up to anywhere with a plate and put food on it, then walk away. But, in times of high traffic, people have a natural tendency to both form lines and stand in existing lines, even if they don't know what the line is for. In this particular case, the line passes along the majority of the buffet area.
Each student knows in advance what they want to eat - they have 1 or more preferred foods, as well as 0 or more substitutions for each. Batched of food are produced on timed intervals, and there can be periods where a particular food is not available at a particular time. We'll say the unit of time is the line of students moving forward to the next food type.
The problem is sorting the students so that, when the line moves along the buffets, as many students as possible get all their preferred foods. Once students have all the foods they want they leave the line. If a student can't get their first choice for one of their foods they'll know to get their next choice for that food while in line - you must avoid the case where the student gets to their first preferred food but that food has run out and they already passed their second preferred food. It's implicitly ok, though, if that happens and their second preferred food is later in the line.
I probably have not mapped out enough details, but this problem is already so complex to me that I can't even think about how to begin solving it. All i can do is think of these basic ways to store the problem state (maybe this will clear up ambiguities):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
enum struct Food
{
//...
};
struct Buffet
{
Food const food_type;
unsigned remaining_food;
unsigned time_until_refill;
unsigned const refill_interval;
unsigned const refill_amount;
};
using Buffets = std::vector<Buffet>;
struct Student
{
using FoodPreferences = std::vector<Food>;
using MissingFoods = std::set<FoodPreferences>;
MissingFoods missing_foods;
};
using Students = std::vector<Student>;
void cafe_sort(Students &line, Buffets const &buffets)
{
//magic
}
|
Again, I thought of all this completely randomly while sitting in the dining hall one day. It's probably too complex with not enough information and it might even have unsolvable scenarios with it's current way of time progression (I don't even know what should happen in the event of a holdup/line split, or if that can be avoided). So, really I'm just interested in if there are similar problems and/or how to fix/refine this problem definition.