Dua Acara Tidak Bertindih Terbaik

2054. Dua Acara Tidak Bertindih Terbaik

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Binari, Pengaturcaraan Dinamik, Isih, Timbunan (Baris Gilir Keutamaan)

Anda diberi 0-diindeks tatasusunan integer 2D acara di mana peristiwa[i] = [StartTime_i, endTime_i, nilai _i]. Acara i^th bermula pada StartTime_i dan berakhir pada endTime_i, dan jika anda menghadiri acara ini, anda akan menerima nilai nilai_i . Anda boleh memilih paling banyak dua acara tidak bertindih untuk dihadiri supaya jumlah nilainya dimaksimumkan.

Kembalikan jumlah maksimum ini.

Perhatikan bahawa masa mula dan masa tamat adalah inklusif: iaitu, anda tidak boleh menghadiri dua acara di mana satu daripadanya bermula dan satu lagi berakhir pada masa yang sama. Lebih khusus lagi, jika anda menghadiri acara dengan masa tamat t, acara seterusnya mesti bermula pada atau selepas t 1.

Contoh 1:

• Input: acara = [[1,3,2],[4,5,2],[2,4,3]]
• Output: 4
• Penjelasan: Pilih acara hijau, 0 dan 1 untuk jumlah 2 2 = 4.

Contoh 2:

• Input: acara = [[1,3,2],[4,5,2],[1,5,5]]
• Output: 5
• Penjelasan: Pilih acara 2 untuk jumlah 5.

Contoh 3:

• Input: acara = [[1,5,3],[1,5,1],[6,6,5]]
• Output: 8
• Penjelasan: Pilih acara 0 dan 2 untuk jumlah 3 5 = 8.

Kekangan:

• 2 <= peristiwa.panjang <= 10⁵
• acara[i].panjang == 3
• 1 <= Masa mula_i <= Masa tamat_i <= 10⁹
• 1 <= nilai_i <= 10⁶

Petunjuk:

1. Bagaimanakah cara mengisih acara berdasarkan masa mulanya dapat membantu? Bagaimana pula dengan zaman akhir?
2. Bagaimanakah kita boleh mendapatkan skor maksimum selang yang tidak bersilang dengan selang yang kita pilih dengan cepat?

Penyelesaian:

Kita boleh menggunakan pendekatan berikut:

Pendekatan

1. Isih Acara mengikut Masa Tamat:

   • Isih membantu kami mencari acara tidak bertindih dengan cekap menggunakan carian binari.

2. Carian Perduaan untuk Acara Tidak Bertindih:

   • Gunakan carian binari untuk mencari acara terbaharu yang berakhir sebelum masa mula acara semasa. Ini memastikan tidak bertindih.

3. Pengaturcaraan Dinamik dengan Penjejakan Maks:

   • Semasa mengulangi acara yang diisih, kekalkan nilai maksimum acara sehingga yang semasa. Ini membolehkan kami mengira jumlah maksimum dua acara dengan cepat.

4. Lelar dan Kira Jumlah Maksimum:

   • Untuk setiap acara, kira jumlah yang mungkin menggunakan:
     • Hanya acara semasa.
     • Acara semasa digabungkan dengan acara tidak bertindih terbaik ditemui menggunakan carian binari.

Mari laksanakan penyelesaian ini dalam PHP: 2054. Dua Acara Tidak Bertindih Terbaik

  
  
  Penjelasan:




Isih:


Acara diisih mengikut masa tamatnya, yang membolehkan carian cekap bagi acara terakhir yang tidak bertindih.



Carian Binari:


Untuk setiap acara, carian binari menentukan acara terbaharu yang berakhir sebelum acara semasa bermula.



Penjejakan Maks:


Kami mengekalkan tatasusunan maxUpTo, yang menyimpan nilai maksimum peristiwa sehingga indeks semasa. Ini mengelakkan pengiraan semula maksimum untuk indeks terdahulu.



Pengiraan Jumlah Maksimum:


Untuk setiap acara, kira jumlah nilainya dan nilai acara tidak bertindih terbaik. Kemas kini jumlah maksimum global dengan sewajarnya.





  
  
  Analisis Kerumitan




Isih: O(n log n)


Carian Perduaan untuk Setiap Acara: O(log n), berulang n kali → O(n log n)


Keseluruhan: O(n log n)



Penyelesaian ini cekap dan berfungsi dengan baik dalam kekangan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Dua Acara Tidak Bertindih Terbaik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!