Before the final round of the TCCC, audience members head to the buffet for lunch.
The buffet line contains a number of food items, in a fixed order.
Those indulging line up at the buffet, each intending to sample a subset of the items available.
It takes each person exactly 10 seconds to help themselves to a food item.
Every 10 seconds, each person moves up as far as they can (without passing by any food they want, of course!). This movement takes no time.
The first person in line moves immediately to each item he wants, in order, spending 10 seconds at each item.
Depending on which items the rest of the people want, they may be able to move up to each item immediately, but also may have to spend some time waiting for the person they are following.
Each person is always either waiting in line before reaching the first food item, standing in front of exactly one food item, or has passed the last food item and is looking for a place to sit.
Two people may not stand in front of the same food item at the same time.
Also, people always remain in the order in which they lined up, and they never move backward in line.
No one ever passes another person in line -- even after they have taken all the food they want, they still exit the buffet in line.
People can only take a food item that they are standing directly in front of.
Anyone who cannot reach the next food item they want (because they are waiting for the person in front of them) will advance as far as possible in line, to avoid blocking the people behind them unnecessarily.
Anxious to get back to the TCCC event, the people wish to get the group through the buffet line as quickly as possible.
Given the list of food items in the buffet and the items that each person wants, return the optimal order in which the people should line up at the buffet so that everyone can get all the food they desire in the least total amount of time.
The food items available at the buffet will be given as a String food.
Each item in food will contain only letters ('a'-'z', 'A'-'Z'), and there will be exactly one space between each pair of adjacent items.
Each item in food will be unique.
The order of items in food is the order they appear in the buffet line, with the first item in food being the first item available.
The items each person wants are given in a String[] cravings.
There will be one element in cravings for each person.
Each element in cravings will be a list of food items found in food, with exactly one space between each food items.
Within each element of cravings, each food item will be unique.
Return a int[] containing the optimal order, where each element is the 0-based index of a person in cravings, and elements are ordered from first to last in line. If there are multiple solutions, return the one that comes first lexicographically. A int[] a1 comes before a int[] a2 lexicographically if, at the first element at which they differ, a1 contains the smaller value.
|