{x}
blog image

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:

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:

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:

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:

  • n == favorite.length
  • 2 <= n <= 105
  • 0 <= favorite[i] <= n - 1
  • favorite[i] != i

Solution Explanation for Maximum Employees to Be Invited to a Meeting

This problem can be modeled as a directed graph where each employee is a node, and a directed edge from employee i to employee favorite[i] represents employee i's preference. The goal is to find the maximum number of employees who can be seated at a circular table such that each employee sits next to their favorite person.

The solution leverages the observation that the graph consists of cycles and trees rooted at the cycle nodes. The optimal solution involves selecting either:

  1. The largest cycle: If a cycle exists, we can seat all employees in that cycle.
  2. Pairs of mutually-favoring employees and their chains: If no large cycles exist, we can identify pairs of employees who mutually favor each other (a cycle of length 2). For each such pair, we can include them and all the employees who favor them (forming a chain). The length of each chain can be determined using topological sort.

The algorithm consists of two main parts:

1. Finding the Largest Cycle:

This part uses Depth-First Search (DFS) to detect cycles in the graph. For each node, it performs DFS until it encounters a previously visited node, indicating a cycle. The length of the longest cycle found is recorded.

2. Finding the Longest Chains from Mutually-Favoring Pairs:

This part utilizes topological sort. We count the number of employees who favor employees in a cycle of length 2. This is done by using indegree (the number of incoming edges) of each node. Nodes with indegree of 0 are added to a queue to start the topological sort. During topological sorting, the longest path from each node in a cycle of length 2 is computed. The sum of lengths of these chains are added to the count.

Time Complexity Analysis:

  • Finding the largest cycle: The DFS process visits each node and edge at most once, resulting in O(N) time complexity, where N is the number of employees.
  • Topological sort: Topological sort also takes O(N) time in the worst case.
  • Overall: The dominant operation is the graph traversal, giving an overall time complexity of O(N).

Space Complexity Analysis:

The space complexity is determined by the auxiliary data structures used:

  • vis: Boolean array to track visited nodes during DFS – O(N)
  • indeg: Integer array to store in-degrees for topological sort – O(N)
  • dist: Integer array to store distances during topological sort – O(N)
  • q: Queue for topological sort – O(N) in the worst case.
  • cycle (in the maxCycle function): List to store nodes in a cycle – O(N) in the worst case.

Thus, the overall space complexity is O(N).

Code Examples (Python):

The Python code provided in the original response efficiently implements this algorithm. The maxCycle function finds the maximum cycle length, while the topologicalSort function finds the sum of lengths of chains rooted in mutually-favoring pairs. The final answer is the maximum of these two values. The code's complexity matches the analysis above.

Note: Other languages (Java, C++, Go, TypeScript) provided in the original response follow the same algorithmic structure and have similar time and space complexities.