Maximale Anzahl an Mitarbeitern, die zu einer Besprechung eingeladen werden können

2127. Maximale Anzahl an Mitarbeitern, die zu einer Besprechung eingeladen werden können

Schwierigkeit:Schwer

Themen: Tiefensuche, Diagramm, Topologische Sortierung

Ein Unternehmen organisiert ein Meeting und hat eine Liste mit n Mitarbeitern, die auf eine Einladung warten. Sie haben einen großen runden Tisch aufgestellt, an dem beliebig viele Mitarbeiter Platz finden.

Die Mitarbeiter sind von 0 bis n - 1 nummeriert. Jeder Mitarbeiter hat eine Lieblingsperson und er nimmt nur dann an der Besprechung teil, wenn er neben seiner Lieblingsperson sitzen kann Tisch. Der Lieblingsmensch eines Mitarbeiters ist nicht er selbst.

Angesichts eines 0-indizierten ganzzahligen Arrays favorite, wobei favorite[i] die Lieblingsperson des i^ten Mitarbeiters bezeichnet, wird die maximale Anzahl zurückgegeben Mitarbeiterdie zur Besprechung eingeladen werden können.

Beispiel 1:

• Eingabe:Favorit = [2,2,1,2]
• Ausgabe: 3
• Erklärung:
  • Die obige Abbildung zeigt, wie das Unternehmen die Mitarbeiter 0, 1 und 2 einladen und an den runden Tisch setzen kann.
  • Es können nicht alle Mitarbeiter eingeladen werden, da Mitarbeiter 2 nicht gleichzeitig neben den Mitarbeitern 0, 1 und 3 sitzen kann.
  • Beachten Sie, dass das Unternehmen auch die Mitarbeiter 1, 2 und 3 einladen und ihnen die gewünschten Plätze zuweisen kann.
  • Die maximale Anzahl der Mitarbeiter, die zu der Besprechung eingeladen werden können, beträgt 3.

Beispiel 2:

• Eingabe:Favorit = [1,2,0]
• Ausgabe: 3
• Erklärung:
  • Jeder Mitarbeiter ist die Lieblingsperson von mindestens einem anderen Mitarbeiter, und das Unternehmen kann ihn nur dann einladen, wenn es jeden Mitarbeiter einlädt.
  • Die Sitzordnung ist die gleiche wie in der Abbildung in Beispiel 1:
  • Mitarbeiter 0 sitzt zwischen Mitarbeiter 2 und 1.
  • Mitarbeiter 1 sitzt zwischen den Mitarbeitern 0 und 2.
  • Mitarbeiter 2 sitzt zwischen den Mitarbeitern 1 und 0.
• Die maximale Anzahl der Mitarbeiter, die zu der Besprechung eingeladen werden können, beträgt 3.

Beispiel 3:

• Eingabe:Favorit = [3,0,1,4,1]
• Ausgabe: 4
• Erklärung:
  • Die obige Abbildung zeigt, wie das Unternehmen die Mitarbeiter 0, 1, 3 und 4 einlädt und sie an den runden Tisch setzt.
  • Mitarbeiter 2 kann nicht eingeladen werden, da die beiden Plätze neben seinem Lieblingsmitarbeiter 1 vergeben sind.
  • Also lässt das Unternehmen sie aus der Besprechung heraus.
  • Die maximale Anzahl der Mitarbeiter, die zu der Besprechung eingeladen werden können, beträgt 4.

Einschränkungen:

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

Hinweis:

1. Erstellen Sie aus dem angegebenen Array favorite einen Graphen, in dem es für jeden Index i eine gerichtete Kante von favorite[i] nach i gibt. Der Graph wird eine Kombination aus Zyklen und Ketten azyklischer Kanten sein. Wie können wir nun Mitarbeiter auswählen, die am Tisch sitzen?
2. Die erste Möglichkeit, Mitarbeiter auszuwählen, besteht darin, einen Zyklus des Diagramms auszuwählen. Es kann nachgewiesen werden, dass in diesem Fall die Mitarbeiter, die nicht im Zyklus liegen, niemals am Tisch sitzen können (es sei denn, der Zyklus hat eine Länge von 2).
3. Der zweite Weg ist die Kombination azyklischer Ketten. Maximal zwei Ketten können durch einen Zyklus der Länge 2 kombiniert werden, wobei jede Kette bei einem der Mitarbeiter im Zyklus endet.

Lösung:

Die Lösung besteht darin, Zyklen und Ketten in dem vom Favoriten-Array gebildeten Diagramm zu analysieren.

Lassen Sie uns diese Lösung in PHP implementieren: 2127. Maximale Anzahl an Mitarbeitern, die zu einer Besprechung eingeladen werden können

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

Erläuterung:

1. Grafikdarstellung:

   • Jeder Mitarbeiter zeigt auf seinen Favoriten und bildet so ein gerichtetes Diagramm.
   • Ein Array indegree wird verwendet, um zu verfolgen, wie viele Mitarbeiter auf jede Person verweisen.

2. Topologische Sortierung für Ketten:

   • Mitarbeiter ohne eingehende Kanten (indegree = 0) werden verarbeitet, um die Kettenlängen zu berechnen, die zu Zyklen führen.

3. Zykluserkennung:

   • Mitarbeiter werden besucht, um Zyklen zu erkennen. Sobald ein Zyklus gefunden wurde:
     • Für Zyklen der Länge 2 werden die an jedem Knoten des Zyklus befestigten Ketten zusammengeführt.
     • Bei längeren Zyklen wird die gesamte Zykluslänge berücksichtigt.

4. Ergebnis:

   • Das Maximum aller Zykluslängen und die Summe der Längen zusammengeführter Ketten aus 2-Längen-Zyklen wird zurückgegeben.

Dieser Ansatz gewährleistet Effizienz mit einer Zeitkomplexität von O(n) und eignet sich daher für große Eingaben bis zu 10⁵.

Kontaktlinks

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie das repository einen Stern auf GitHub geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken teilen? Ihre Unterstützung würde mir viel bedeuten!

Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

• linkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonMaximale Anzahl an Mitarbeitern, die zu einer Besprechung eingeladen werden können. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!