The games now need to be scheduled, which will happen in two steps. Your first task is to group
together games that can be played simultaneously into game groups. The requirements for the game
groups are:
• People are not double-booked: each person is involved in at most one game in any game group.,
either as a player or referee
• Games are played once: each game is in exactly one game group
Each game group will be played in a single time slot, so the committee wants the smallest number of
game groups possible.
Implement your solution as a Python function of the form
def gameGroups ( assignedReferees ):
where assignedReferees is in the same format as you returned in the previous question, i.e. as a
dictionary with games as keys and referees as values. Your output should be a schedule in a data
structure of the form
Page 2
# list of timeslots
# each timeslot is a set of games
# each game is a pair ( player1 , player2 )
[
{ ( " Ashley " , " Bob " ) , ( " Charlie " , " Dave " ) } ,
{ ( " Bob " , " Charlie " ) , ( " Rene " , " Elaine " ) }
]

Question

The games now need to be scheduled, which will happen in two steps. Your first task is to group
together games that can be played simultaneously into game groups. The requirements for the game
groups are:
• People are not double-booked: each person is involved in at most one game in any game group.,
either as a player or referee
• Games are played once: each game is in exactly one game group
Each game group will be played in a single time slot, so the committee wants the smallest number of
game groups possible.
Implement your solution as a Python function of the form
def gameGroups ( assignedReferees ):
where assignedReferees is in the same format as you returned in the previous question, i.e. as a
dictionary with games as keys and referees as values. Your output should be a schedule in a data
structure of the form
Page 2
# list of timeslots
# each timeslot is a set of games
# each game is a pair ( player1 , player2 )
[
{ ( " Ashley " , " Bob " ) , ( " Charlie " , " Dave " ) } ,
{ ( " Bob " , " Charlie " ) , ( " Rene " , " Elaine " ) }
]

Accepted Answer

```python # define a function named gameGroups def gameGroups(assignedReferees): # Create a list to hold the game groups (time slots) game_groups = [] # Create a set to keep track of people who are already scheduled in the current time slot scheduled_people = set() # Iterate over the games and their assigned referees for game, referee in assignedReferees.items(): player1, player2 = game # Check if any of the players or the referee are already scheduled in the current time slot if player1 in scheduled_people or player2 in scheduled_people or referee in scheduled_people: # If they are, create a new time slot (game group) game_groups.append(set()) scheduled_people = set() # Add the game to the current time slot game_groups[-1].add(game) # Add the players and the referee to the scheduled people set scheduled_people.update([player1, player2, referee]) return game_groups ``` ```python # main function that tests gameGroups def main_gameGroups(): # test the gameGroups function # use case 1 assignedReferees1 = { ("Ashley", "Bob"): "Ref1", ("Charlie", "Dave"): "Ref2", ("Bob", "Charlie"): "Ref3", ("Rene", "Elaine"): "Ref4" } assert gameGroups(assignedReferees1) == [ {("Ashley", "Bob"), ("Charlie", "Dave")}, {("Bob", "Charlie"), ("Rene", "Elaine")} ] # use case 2 assignedReferees2 = { ("Alice", "Bob"): "Ref1", ("Charlie", "Dave"): "Ref2", ("Eve", "Frank"): "Ref3", ("George", "Hank"): "Ref4" } assert gameGroups(assignedReferees2) == [ {("Alice", "Bob"), ("Charlie", "Dave"), ("Eve", "Frank"), ("George", "Hank")} ] # Run the main function to test the gameGroups function main_gameGroups() ``` ∻Explanation∻ ⚹The function `gameGroups` groups games into time slots such that no person is double-booked.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Define the main function required here: `gameGroups` which takes a dictionary of assigned referees. ‖ ‖ ▪ ⋮ Create a list to hold the game groups (time slots). ‖ ‖ ▪ ⋮ Create a set to keep track of people who are already scheduled in the current time slot. ‖ ‖ ▪ ⋮ Iterate over the games and their assigned referees. ‖ ‖ ▪ ⋮ Check if any of the players or the referee are already scheduled in the current time slot. ‖ ‖ ▪ ⋮ If they are, create a new time slot (game group). ‖ ‖ ▪ ⋮ Add the game to the current time slot. ‖ ‖ ▪ ⋮ Add the players and the referee to the scheduled people set. ‖ ‖ ▪ ⋮ Return the list of game groups. ‖ ∻Time Complexity∻ ⚹The time complexity is $O(n)$ where $n$ is the number of games.⚹ ∻Space Complexity∻ ⚹The space complexity is $O(n)$ for storing the game groups and scheduled people.⚹

Sia