회의에 초대 될 최대 직원

2127. 회의에 초대할 수 있는 최대 직원수

난이도:어려움

주제: 깊이 우선 검색, 그래프, 위상 정렬

한 회사에서 회의를 조직하고 있으며 초대를 기다리고 있는 n명의 직원 목록이 있습니다. 원하는 수명의 직원

이 앉을 수 있는 대형 원형 테이블을 마련했습니다.

직원 번호는 0부터 n - 1까지입니다. 각 직원에게는 좋아하는 사람이 있으며 회의에 참석할 수 있는 사람은 오직 자신이 좋아하는 사람 옆에 앉을 수 있는 경우입니다. 테이블. 직원이 가장 좋아하는 사람은 자신이 아닙니다

인덱스가 0인 정수 배열 즐겨찾기가 주어지고, 여기서 favorite[i]는 i^번째 직원이 가장 좋아하는 사람을 나타내며, 최대 개수를 반환합니다. 회의에 초대할 수 있는 직원.

예 1:

• 입력: favorite = [2,2,1,2]
• 출력: 3
• 설명:
  • 위 그림은 회사에서 직원 0, 1, 2를 초대하여 원탁에 앉히는 모습을 보여줍니다.
  • 직원 2는 직원 0, 1, 3 옆에 동시에 앉을 수 없기 때문에 모든 직원을 초대할 수 없습니다.
  • 회사에서 직원 1, 2, 3을 초대해 원하는 자리를 배정할 수도 있다는 점 참고하세요.
  • 회의에 초대할 수 있는 최대 직원 수는 3명입니다.

예 2:

• 입력: 즐겨찾기 = [1,2,0]
• 출력: 3
• 설명:
  • 각 직원은 적어도 한 명의 다른 직원이 가장 좋아하는 사람이며, 회사가 그들을 초대할 수 있는 유일한 방법은 모든 직원을 초대하는 것입니다.
  • 좌석 배치는 예시 1의 그림과 동일합니다.
  • 직원 0은 직원 2와 1 사이에 앉습니다.
  • 직원 1은 직원 0과 2 사이에 앉습니다.
  • 직원 2는 직원 1과 0 사이에 앉습니다.
• 회의에 초대할 수 있는 최대 직원 수는 3명입니다.

예 3:

• 입력: favorite = [3,0,1,4,1]
• 출력: 4
• 설명:
  • 위 그림은 회사에서 직원 0, 1, 3, 4를 초대하여 원탁에 앉히는 모습을 보여줍니다.
  • 직원 2는 자신이 가장 좋아하는 직원 1 옆의 두 자리가 이미 차 있기 때문에 초대할 수 없습니다.
  • 그래서 회사에서는 그들을 회의에서 제외시켰습니다.
  • 회의에 초대할 수 있는 최대 직원 수는 4명입니다.

제약조건:

• n == favorite.length
• 2 5
• 0
• favorite[i] != i

힌트:

1. 주어진 즐겨찾기 배열에서 모든 인덱스 i에 대해 favorite[i]에서 i로 향하는 가장자리가 있는 그래프를 만듭니다. 그래프는 비순환 모서리의 순환과 체인의 조합입니다. 자, 테이블에 앉을 직원을 선택하는 방법은 무엇입니까?
2. 직원을 선택하는 첫 번째 방법은 그래프의 주기를 선택하는 것입니다. 이 경우 사이클에 누워 있지 않은 직원은 테이블에 앉을 수 없다는 것이 입증될 수 있습니다(사이클의 길이가 2인 경우 제외).
3. 두 번째 방법은 비고리형 체인을 결합하는 것입니다. 최대 두 개의 체인은 길이 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
?>

설명:

1. 그래프 표현:

   • 직원 각자가 자신이 좋아하는 것을 가리키며 유향 그래프를 형성합니다.
   • 각 사람을 가리키는 직원 수를 추적하는 데 배열 indegree가 사용됩니다.

2. 체인의 위상 정렬:

   • 인커밍 에지가 없는 직원(도수 = 0)을 처리하여 순환으로 이어지는 체인 길이를 계산합니다.

3. 주기 감지:

   • 직원들을 방문하여 주기를 감지합니다. 사이클이 발견되면:
     • 길이가 2인 주기의 경우 주기의 각 노드에 연결된 체인이 병합됩니다.
     • 사이클이 길어질 경우 전체 사이클 길이가 고려됩니다.

4. 결과:

   • 모든 사이클 길이의 최대값과 2개의 길이 사이클에서 병합된 체인 길이의 합이 반환됩니다.

이 접근 방식은 O(n)의 시간 복잡도로 효율성을 보장하므로 최대 10⁵.

연락처 링크이 시리즈가 도움이된다면 리포지토리

를 Github의 별에게 제공하거나 좋아하는 소셜 네트워크에서 게시물을 공유하는 것이 무엇입니까? 당신의 지원은 나에게 큰 의미가 있습니다! 이와 같은 유용한 콘텐츠를 원한다면 언제든지 나를 따르십시오 :

LinkedIn

github

위 내용은 회의에 초대 될 최대 직원의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!