Several children want turns on a video game machine. Each turn takes one time slot, and only one child can play during a slot.

A child may request multiple turns. After finishing a turn, that child must wait for a fixed number of complete slots before playing again.

Other children may play during the waiting period. If no child is currently allowed to play, the machine remains unused for that slot.

The requested turns may be arranged in any order. Find the minimum number of time slots needed to complete every requested turn.

Class

GameMachinePlanner

Method

minimumSlots

public int minimumSlots(List<String> turnRequests, int waitingSlots)

• Each element of turnRequests is the name of a child requesting one turn.
• If a name appears multiple times, that child has requested multiple turns.
• waitingSlots is the minimum number of complete slots that must occur between two turns taken by the same child.
• Returns the minimum total number of slots needed, including unused slots.

Rules

• Every requested turn must be completed exactly once.
• Only one child may play during each slot.
• The requested turns may be completed in any order.
• A waiting slot may be used by another child or may remain unused.
• The supplied turnRequests list must not be modified.

Constraints

• 1 ≤ turnRequests.size() ≤ 10,000
• 1 ≤ turnRequests.get(i).length() ≤ 20
• Every name contains only English letters.
• Names are compared case-insensitively. For example, "gaurav" and "GauRav" represent the same child, and their requested turns must be counted together.
• 0 ≤ waitingSlots ≤ 100
• turnRequests and its elements are never null.

Examples

Example 1

minimumSlots( turnRequests = List.of("Aarav", "Aarav", "Aarav", "Aarav", "Diya", "Diya", "Diya", "Kabir"), waitingSlots = 2)

Output: 10

One optimal arrangement is: Aarav, Diya, Kabir, Aarav, Diya, unused, Aarav, Diya, unused, Aarav.

Example 2

minimumSlots( turnRequests = List.of("Mira", "Rohan", "Mira", "Tara", "Rohan", "Neel", "Mira"), waitingSlots = 1)

Output: 7

The children can be arranged so that every slot is used while leaving at least one complete slot between repeated turns of the same child.

Example 3

minimumSlots( turnRequests = List.of("Ishaan", "Ishaan", "Ishaan", "Ishaan", "Zoya", "Zoya"), waitingSlots = 3)

Output: 13

There are not enough turns from other children to fill every waiting period, so some slots must remain unused.