We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Employees to Be Invited to a Meeting

Difficulty: Hard

Problem Description

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. 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. Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the i-th employee, return the maximum number of employees that can be invited to the meeting.

Key Insights

  • Employees can only attend the meeting if they are seated next to their favorite person.
  • The problem can be visualized as a directed graph where each employee points to their favorite.
  • The solution involves detecting cycles and determining how many employees can be seated based on mutual favorites.
  • There are different configurations based on cycles and paths in the graph.

Space and Time Complexity

Time Complexity: O(n), where n is the number of employees. Each employee is processed once. Space Complexity: O(n), for storing the graph and visited states.

Solution

To solve the problem, we represent the employees and their favorite relationships as a directed graph. We perform a Depth-First Search (DFS) to explore the graph and find cycles. We need to track visited nodes to prevent reprocessing. For each cycle found, we count the employees involved and determine how many can be invited based on their seating arrangement. The algorithm effectively calculates the maximum number of employees that can be invited while respecting their seating preferences.

Code Solutions

def maxEmployees(favorite):
    n = len(favorite)
    visited = [0] * n
    graph = [[] for _ in range(n)]
    
    for i in range(n):
        graph[favorite[i]].append(i)
    
    def dfs(node):
        if visited[node] != 0:
            return visited[node]
        visited[node] = -1  # mark as visiting
        cycle_size = 0
        for neighbor in graph[node]:
            result = dfs(neighbor)
            if result == -1:  # cycle detected
                return -1
            cycle_size += result
        visited[node] = cycle_size + 1
        return visited[node]

    max_invite = 0
    for i in range(n):
        if visited[i] == 0:
            result = dfs(i)
            if result != -1:
                max_invite += result
    
    return max_invite
← Back to All Questions