Nombre maximum d'employés pouvant être invités à une réunion

2127. Nombre maximum d'employés à inviter à une réunion

Difficulté : Difficile

Sujets : Recherche en profondeur, graphique, tri topologique

Une entreprise organise une réunion et dispose d'une liste de n salariés, en attente d'être invités. Ils ont aménagé une grande table circulaire, capable d'accueillir n'importe quel nombre d'employés.

Les employés sont numérotés de 0 à n - 1. Chaque employé a une personne préférée et ils assisteront à la réunion seulement si ils peuvent s'asseoir à côté de leur personne préférée au tableau. La personne préférée d'un employé n'est pas lui-même.

Étant donné un tableau d'entiers indexé à 0 favori, où favori[i] désigne la personne préférée du i^ème employé, renvoie le nombre maximum de salariésqui peuvent être invités à la réunion.

Exemple 1 :

• Entrée : favori = [2,2,1,2]
• Sortie : 3
• Explication :
  • La figure ci-dessus montre comment l'entreprise peut inviter les employés 0, 1 et 2 et les asseoir à la table ronde.
  • Tous les employés ne peuvent pas être invités car l'employé 2 ne peut pas s'asseoir simultanément à côté des employés 0, 1 et 3.
  • À noter que l'entreprise peut également inviter les salariés 1, 2 et 3, et leur attribuer les sièges souhaités.
  • Le nombre maximum de salariés pouvant être invités à la réunion est de 3.

Exemple 2 :

• Entrée : favori = [1,2,0]
• Sortie : 3
• Explication :
  • Chaque employé est la personne préférée d'au moins un autre employé, et la seule façon pour l'entreprise de les inviter est d'inviter tous les employés.
  • La disposition des sièges sera la même que celle de la figure donnée dans l'exemple 1 :
  • L'employé 0 sera assis entre les employés 2 et 1.
  • L'employé 1 sera assis entre les employés 0 et 2.
  • L'employé 2 sera assis entre les employés 1 et 0.
• Le nombre maximum de salariés pouvant être invités à la réunion est de 3.

Exemple 3 :

• Entrée: favori = [3,0,1,4,1]
• Sortie: 4
• Explication:
  • La figure ci-dessus montre comment l'entreprise invitera les employés 0, 1, 3 et 4, et les asseoir à la table ronde.
  • Employé 2 ne peut pas être invité car les deux spots à côté de leur employé préféré 1 sont pris.
  • donc l'entreprise les laisse hors de la réunion.
  • Le nombre maximum d'employés qui peuvent être invités à la réunion est de 4.

Contraintes:

• n == favori.length
• 2 & lt; = n & lt; = 10 ⁵
• 0 & lt; = favori [i] & lt; = n - 1
• favori [i]! = I

Indice:

1. À partir du favori du tableau donné, créez un graphique où pour chaque index i, il y a un bord dirigé de Favorite [i] à i. Le graphique sera une combinaison de cycles et de chaînes de bords acycliques. Maintenant, quelles sont les façons dont nous pouvons choisir les employés pour s'asseoir à la table?
2. La première façon par laquelle nous pouvons choisir les employés est de sélectionner un cycle du graphique. On peut prouver que dans ce cas, les employés qui ne se trouvent pas dans le cycle ne peuvent jamais être assis à la table (sauf si le cycle a une longueur de 2).
3. La deuxième voie est de combiner les chaînes acycliques. Au plus, deux chaînes peuvent être combinées par un cycle de longueur 2, où chaque chaîne se termine sur l'un des employés du cycle.

Solution:

La solution consiste à analyser les cycles et les chaînes dans le graphique formé par le tableau préféré.

implémentons cette solution dans PHP: 2127. Les employés maximaux à inviter à une réunion

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

Explication:

1. Représentation du graphique :

   • Chaque employé pointe vers leur préféré, formant un graphique dirigé.
   • Un INDEGREE UN TABLEAU est utilisé pour garder une trace du nombre d'employés pointer à chaque personne.

2. Toi topologique pour les chaînes :

   • Les employés sans bords entrants (indegree = 0) sont traités pour calculer les longueurs de chaîne conduisant à des cycles.

3. Détection du cycle :

   • Les employés sont visités pour détecter les cycles. Une fois un cycle trouvé:
     • Pour les cycles de longueur 2, les chaînes attachées à chaque nœud du cycle sont fusionnées.
     • Pour les cycles plus longs, la longueur du cycle entier est considérée.

4. Résultat :

   • Le maximum de toutes les longueurs de cycle et la somme des longueurs des chaînes fusionnées à partir de cycles de 2 longueurs sont renvoyées.

Cette approche assure l'efficacité avec une complexité temporelle de o (n) , ce qui le rend adapté à de grandes entrées jusqu'à 10 ⁵ .

Contact Links

Si vous avez trouvé cette série utile, veuillez envisager de donner le dépositaire une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

• LinkedIn
• github

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!