A person wants to complete a food-tasting challenge containing several food items. Each food item must be eaten exactly once.

Some food items may be eaten only after certain other items have been eaten in earlier meals. At most maxItemsPerMeal items may be eaten during one meal.

Find the minimum number of meals required to eat every food item.

Class

FoodTastingPlanner

Method

Minimum Meals

public int minimumMeals(int foodItemCount, List<String> eatingRules, int maxItemsPerMeal)

• foodItemCount is the number of food items, labeled from 1 through foodItemCount.
• Every element of eatingRules uses the format "requiredItem,laterItem".
• A rule "a,b" means item a must be eaten before item b.
• maxItemsPerMeal is the maximum number of items that may be eaten during one meal.
• Returns the minimum number of meals required to eat all items.

Eating Rules

• An item is available at the beginning of a meal only when all its required earlier items were eaten in previous meals.
• Items eaten during the same meal cannot make another item available in that meal.
• If at most maxItemsPerMeal items are available, all of them may be eaten.
• If more items are available, exactly maxItemsPerMeal of them may be selected.
• When more than maxItemsPerMeal items are available, the returned result must be the minimum over all valid choices of exactly maxItemsPerMeal available items.
• The supplied eatingRules list must not be modified.

Constraints

• 1 ≤ foodItemCount ≤ 15
• 0 ≤ eatingRules.size() ≤ foodItemCount * (foodItemCount - 1) / 2
• 1 ≤ maxItemsPerMeal ≤ foodItemCount
• Every eating rule contains exactly two comma-separated item identifiers with no whitespace.
• For every rule "a,b", 1 ≤ a, b ≤ foodItemCount and a != b.
• All eating rules are unique.
• The eating rules do not contain a dependency cycle.

Examples

Example 1

minimumMeals(foodItemCount = 7, eatingRules = ["1,5", "2,5", "3,6", "4,6", "5,7", "6,7"], maxItemsPerMeal = 2)

Output: 4

One optimal plan is to eat items 1 and 3, then items 2 and 4, followed by items 5 and 6, and finally item 7.

Example 2

minimumMeals(foodItemCount = 5, eatingRules = [], maxItemsPerMeal = 2)

Output: 3

All items are initially available. Two items can be eaten during each of the first two meals, followed by the remaining item.

Example 3

minimumMeals(foodItemCount = 6, eatingRules = ["1,2", "2,3", "3,4"], maxItemsPerMeal = 3)

Output: 4

Items 1, 2, 3, and 4 must be eaten in four different meals. Items 5 and 6 can be eaten alongside them.