Pekerja maksimum untuk dijemput ke mesyuarat

2127. Pekerja maksimum untuk dijemput ke mesyuarat

Kesukaran: Hard

topik: carian kedalaman-pertama, graf, jenis topologi

Sebuah syarikat sedang menganjurkan mesyuarat dan mempunyai senarai pekerja N, menunggu untuk dijemput. Mereka telah mengatur meja pekeliling yang besar, mampu duduk mana -mana nombor pekerja.

pekerja bernombor dari 0 hingga n - 1. Setiap pekerja mempunyai orang kegemaran dan mereka akan menghadiri mesyuarat hanya jika Jadual. Orang kegemaran seorang pekerja adalah tidak sendiri.

diberikan 0-indexed integer array kegemaran, di mana kegemaran [i] menandakan orang kegemaran pekerja i yang boleh dijemput ke mesyuarat . Contoh 1:

input: kegemaran = [2,2,1,2]

• output: 3
• Penjelasan:
angka di atas menunjukkan bagaimana syarikat boleh menjemput pekerja 0, 1, dan 2, dan duduk di meja bulat.
• Semua pekerja tidak boleh dijemput kerana Pekerja 2 tidak boleh duduk di samping pekerja 0, 1, dan 3, secara serentak.
  Perhatikan bahawa syarikat itu juga boleh menjemput pekerja 1, 2, dan 3, dan memberi mereka kerusi yang dikehendaki.
  bilangan maksimum pekerja yang boleh dijemput ke mesyuarat ialah 3.
  Contoh 2:

input: kegemaran = [1,2,0]

• output: 3
• Penjelasan:
Setiap pekerja adalah orang kegemaran sekurang -kurangnya seorang pekerja lain, dan satu -satunya cara syarikat dapat menjemput mereka adalah jika mereka menjemput setiap pekerja.
• Pengaturan tempat duduk akan sama seperti yang diberikan dalam Rajah 1:
  Pekerja 0 akan duduk di antara pekerja 2 dan 1.
  Pekerja 1 akan duduk di antara pekerja 0 dan 2.
  Pekerja 2 akan duduk di antara pekerja 1 dan 0.
  bilangan maksimum pekerja yang boleh dijemput ke mesyuarat ialah 3.
Contoh 3:

• input: kegemaran = [3,0,1,4,1]
• output: 4
• Penjelasan:
  • angka di atas menunjukkan bagaimana syarikat akan menjemput pekerja 0, 1, 3, dan 4, dan duduk di meja bulat.
  • Pekerja 2 tidak dapat dijemput kerana kedua -dua tempat di sebelah pekerja kegemaran mereka 1 diambil.
  • jadi syarikat meninggalkan mereka keluar dari mesyuarat.
  • bilangan maksimum pekerja yang boleh dijemput ke mesyuarat ialah 4.

Kekangan:

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

Petunjuk:

1. Dari kegemaran array yang diberikan, buat graf di mana untuk setiap indeks I, terdapat kelebihan yang diarahkan dari kegemaran [i] kepada i. Grafik akan menjadi gabungan kitaran dan rantai tepi aciklik. Sekarang, apakah cara kita boleh memilih pekerja untuk duduk di meja?
2. Cara pertama yang boleh kita pilih pekerja adalah dengan memilih kitaran graf. Ia dapat dibuktikan bahawa dalam kes ini, pekerja yang tidak terletak pada kitaran tidak boleh duduk di meja (kecuali kitaran mempunyai panjang 2).
3. Cara kedua adalah dengan menggabungkan rantai acyclic. Paling banyak dua rantai boleh digabungkan dengan kitaran panjang 2, di mana setiap rantai berakhir pada salah satu pekerja dalam kitaran.

Penyelesaian:

Penyelesaian ini melibatkan menganalisis kitaran dan rantai dalam graf yang dibentuk oleh array kegemaran.

mari kita melaksanakan penyelesaian ini dalam php: 2127. Pekerja maksimum untuk dijemput ke mesyuarat

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

Penjelasan:

1. Perwakilan graf :

   • setiap pekerja menunjukkan kegemaran mereka, membentuk graf yang diarahkan.
   • Indegre array digunakan untuk menjejaki berapa banyak pekerja menunjuk kepada setiap orang.

2. jenis topologi untuk rantai :

   • Pekerja tanpa tepi masuk (indegree = 0) diproses untuk mengira panjang rantai yang membawa kepada kitaran.

3. Pengesanan kitaran :

   • Pekerja dikunjungi untuk mengesan kitaran. Setelah kitaran dijumpai:
     • Untuk kitaran panjang 2, rantai yang dilampirkan pada setiap nod kitaran digabungkan.
     • Untuk kitaran yang lebih panjang, panjang keseluruhan kitaran dipertimbangkan.

4. Hasil :

   • maksimum semua panjang kitaran dan jumlah panjang rantai yang digabungkan dari kitaran 2 panjang dikembalikan.

Pendekatan ini memastikan kecekapan dengan kerumitan masa o (n) , menjadikannya sesuai untuk input besar sehingga 10 ⁵ .

Pautan kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberikan repositori bintang di GitHub atau berkongsi jawatan di rangkaian sosial kegemaran anda? Sokongan anda sangat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, jangan ragu untuk mengikuti saya:

• LinkedIn
• github

Atas ialah kandungan terperinci Pekerja maksimum untuk dijemput ke mesyuarat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!