2246 Maximum Employees To Be Invited To A Meeting
2246 Maximum Employees To Be Invited To A Meeting
Maximum Employees to Be Invited to a Meeting 
A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees.
The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself.
Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.
Example 1:
1
2
3
4
5
6
7
8
9
**Input:** favorite = [2,2,1,2]
**Output:** 3
**Explanation:**
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3.
Example 2:
1
2
3
4
5
6
7
8
9
10
11
**Input:** favorite = [1,2,0]
**Output:** 3
**Explanation:**
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.
Example 3:
1
2
3
4
5
6
7
8
9
**Input:** favorite = [3,0,1,4,1]
**Output:** 4
**Explanation:**
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.
Constraints:
1
2
3
4
n == favorite.length
2 <= n <= 105
0 <= favorite[i] <= n - 1
favorite[i] != i
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
# Calculate the maximum distance from a given start node
def _bfs(
start_node: int, visited_nodes: set, reversed_graph: List[List[int]]
) -> int:
# Queue to store nodes and their distances
queue = deque([(start_node, 0)])
max_distance = 0
while queue:
current_node, current_distance = queue.popleft()
for neighbor in reversed_graph[current_node]:
if neighbor in visited_nodes:
continue # Skip already visited nodes
visited_nodes.add(neighbor)
queue.append((neighbor, current_distance + 1))
max_distance = max(max_distance, current_distance + 1)
return max_distance
num_people = len(favorite)
reversed_graph = [[] for _ in range(num_people)]
# Build the reversed graph where each node points to its admirers
for person in range(num_people):
reversed_graph[favorite[person]].append(person)
longest_cycle = 0
two_cycle_invitations = 0
visited = [False] * num_people
# Find all cycles in the graph
for person in range(num_people):
if not visited[person]:
# Track visited persons and their distances
visited_persons = {}
current_person = person
distance = 0
while True:
if visited[current_person]:
break
visited[current_person] = True
visited_persons[current_person] = distance
distance += 1
next_person = favorite[current_person]
# Cycle detected
if next_person in visited_persons:
cycle_length = distance - visited_persons[next_person]
longest_cycle = max(longest_cycle, cycle_length)
# Handle cycles of length 2
if cycle_length == 2:
visited_nodes = {current_person, next_person}
two_cycle_invitations += (
2
+ _bfs(
next_person, visited_nodes, reversed_graph
)
+ _bfs(
current_person,
visited_nodes,
reversed_graph,
)
)
break
current_person = next_person
return max(longest_cycle, two_cycle_invitations)
This post is licensed under CC BY 4.0 by the author.