邀請最大的員工參加會議-php教程-PHP中文網

邀請最大的員工參加會議

Patricia Arquette

發布： 2025-01-27 02:04:10

原創

292 人瀏覽過

2127。受邀參加會議的員工數量上限

難度：難

主題：深度優先搜索、圖、拓撲排序

某公司正在組織一次會議，有一份 n 名員工的名單，等待被邀請。他們安排了一張大圓桌，可以容納任意數量名員工。

員工編號從 0 到 n - 1。每個員工都有一個最喜歡的人，他們才會參加會議只有他們可以坐在他們最喜歡的人旁邊桌子。員工最喜歡的人不是

他們自己。

給定一個0索引^{整數數組favorite，其中favorite[i]表示第i}第個員工最喜歡的人，返回最大數量可以受邀參加會議的員工

。

示例1：

邀請最大的員工參加會議

輸入：
輸出：
說明：

示例2：

輸入：
輸出：
說明：

示例 3：

邀請最大的員工參加會議

輸入： 最喜歡的 = [3,0,1,4,1]
輸出： 4
說明：
- 上圖展示了公司如何邀請員工0、1、3、4，並讓他們坐在圓桌旁。
- 員工 2 無法被邀請，因為他們最喜歡的員工 1 旁邊的兩個位置已被佔用。
- 因此公司將他們排除在會議之外。
- 最多可邀請參加會議的員工人數為 4 人。

約束：

n == 最喜歡的.length
2 5
0
最喜歡的[i] != i

提示：

根據給定的陣列 favorite，建立一個圖，其中對於每個索引 i，都有一條從 favorite[i] 到 i 的有向邊。此圖將是循環和非循環邊鏈的組合。那麼，我們可以透過哪些方式來選擇員工呢？
我們選擇員工的第一種方法是選擇圖表的周期。可以證明，在這種情況下，不在循環中的員工永遠不可能坐在桌子上（除非循環長度為2）。
第二種方法是組合無環鏈。最多可以透過長度為 2 的循環組合兩條鏈，其中每條鏈都以循環中的一名僱員為結束。

解：

解決方案涉及分析由最喜歡的數組形成的圖中的循環和鏈。

讓我們用 PHP 實作這個解：2127。受邀參加會議的員工人數上限

<?php /**
 * @param Integer[] $favorite
 * @return Integer
 */
function maximumInvitations($favorite) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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
?>

登入後複製

解釋：

圖形表示:
- 每個員工都指向自己最喜歡的，形成一個有向圖。
- 數組入度用於追蹤有多少員工指向每個人。
鏈的拓樸排序:
- 沒有傳入邊（入度 = 0）的員工將被處理以計算導致循環的鍊長度。
週期偵測:
- 拜訪員工以偵測週期。一旦找到循環：
  - 對於長度為 2 的循環，連接到循環每個節點的鏈將被合併。
  - 對於較長的週期，會考慮整個週期的長度。
結果：
- 傳回所有循環長度的最大值以及2個長度循環的合併鍊長度總和。