2127. Maximum Employees to Be Invited to a Meeting

[mah-shamim]

Topics: Depth-First Search, Graph, Topological Sort

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

Hint:

1. From the given array favorite, create a graph where for every index i, there is a directed edge from favorite[i] to i. The graph will be a combination of cycles and chains of acyclic edges. Now, what are the ways in which we can choose employees to sit at the table?
2. The first way by which we can choose employees is by selecting a cycle of the graph. It can be proven that in this case, the employees that do not lie in the cycle can never be seated at the table (unless the cycle has a length of 2).
3. The second way is by combining acyclic chains. At most two chains can be combined by a cycle of length 2, where each chain ends on one of the employees in the cycle.

[mah-shamim]

The solution involves analyzing cycles and chains in the graph formed by the favorite array.

Let's implement this solution in PHP: 2127. Maximum Employees to Be Invited to a Meeting

<?php
/**
 * @param Integer[] $favorite
 * @return Integer
 */
function maximumInvitations($favorite) {
    $n = count($favorite);

    // Step 1: Build graph and indegree array
    $indegree = array_fill(0, $n, 0);
    $graph = array_fill(0, $n, []);

    for ($i = 0; $i < $n; $i++) {
        $indegree[$favorite[$i]]++;
        $graph[$favorite[$i]][] = $i;
    }

    // Step 2: Process chains (using topological sort to find chains)
    $queue = [];
    for ($i = 0; $i < $n; $i++) {
        if ($indegree[$i] === 0) {
            $queue[] = $i;
        }
    }

    $chainLengths = array_fill(0, $n, 0);
    while (!empty($queue)) {
        $current = array_pop($queue);
        $fav = $favorite[$current];
        $chainLengths[$fav] = max($chainLengths[$fav], $chainLengths[$current] + 1);
        if (--$indegree[$fav] === 0) {
            $queue[] = $fav;
        }
    }

    // Step 3: Process cycles
    $visited = array_fill(0, $n, false);
    $maxCycleLength = 0;
    $totalChainSum = 0;

    for ($i = 0; $i < $n; $i++) {
        if (!$visited[$i]) {
            $current = $i;
            $cycleNodes = [];

            // Detect cycle
            while (!$visited[$current]) {
                $visited[$current] = true;
                $cycleNodes[] = $current;
                $current = $favorite[$current];
            }

            // Check if we found a cycle
            if (in_array($current, $cycleNodes)) {
                $cycleStartIndex = array_search($current, $cycleNodes);
                $cycle = array_slice($cycleNodes, $cycleStartIndex);
                $cycleLength = count($cycle);

                if ($cycleLength == 2) {
                    // Handle special case of 2-length cycles (merge chains)
                    $node1 = $cycle[0];
                    $node2 = $cycle[1];
                    $totalChainSum += $chainLengths[$node1] + $chainLengths[$node2] + 2;
                } else {
                    // Regular cycle
                    $maxCycleLength = max($maxCycleLength, $cycleLength);
                }
            }
        }
    }

    return max($maxCycleLength, $totalChainSum);
}

// Example usage:
$favorites1 = [2, 2, 1, 2];
$favorites2 = [1, 2, 0];
$favorites3 = [3, 0, 1, 4, 1];

echo maximumInvitations($favorites1) . "\n"; // Output: 3
echo maximumInvitations($favorites2) . "\n"; // Output: 3
echo maximumInvitations($favorites3) . "\n"; // Output: 4
?>

Explanation:

1. Graph Representation:

   • Each employee points to their favorite, forming a directed graph.
   • An array indegree is used to keep track of how many employees point to each person.

2. Topological Sort for Chains:

   • Employees without incoming edges (indegree = 0) are processed to calculate the chain lengths leading to cycles.

3. Cycle Detection:

   • Employees are visited to detect cycles. Once a cycle is found:
     • For cycles of length 2, the chains attached to each node of the cycle are merged.
     • For longer cycles, the entire cycle's length is considered.

4. Result:

   • The maximum of all cycle lengths and the sum of the lengths of merged chains from 2-length cycles is returned.

This approach ensures efficiency with a time complexity of O(n), making it suitable for large inputs up to 10⁵.

[topugit]

Thanks for solving the problem of "Maximum Employees to Be Invited to a Meeting"

[mah-shamim]

Thanks