Zwei beste sich nicht überschneidende Ereignisse

2054. Zwei beste sich nicht überschneidende Events

Schwierigkeit:Mittel

Themen:Array, Binäre Suche, Dynamische Programmierung, Sortierung, Heap (Prioritätswarteschlange)

Sie erhalten ein 0-indiziertes 2D-Integer-Array von Ereignissen, wobei events[i] = [startTime_i, endTime_i, value _{ist ich}]. Die i^te Veranstaltung beginnt bei startTime_i und endet bei endTime_i, und wenn Sie an dieser Veranstaltung teilnehmen, erhalten Sie einen Wert von value_i . Sie können maximal zwei sich nicht überschneidende Veranstaltungen auswählen, an denen Sie teilnehmen möchten, sodass die Summe ihrer Werte maximiert ist.

Diese maximale Summe zurückgeben.

Beachten Sie, dass die Start- und Endzeit inklusive ist: Das heißt, Sie können nicht an zwei Veranstaltungen teilnehmen, bei denen eine beginnt und die andere gleichzeitig endet. Genauer gesagt: Wenn Sie an einer Veranstaltung mit Endzeit t teilnehmen, muss die nächste Veranstaltung bei oder nach t 1 beginnen.

Beispiel 1:

• Eingabe: Ereignisse = [[1,3,2],[4,5,2],[2,4,3]]
• Ausgabe: 4
• Erklärung:Wählen Sie die grünen Ereignisse 0 und 1 für eine Summe von 2 2 = 4.

Beispiel 2:

• Eingabe: Ereignisse = [[1,3,2],[4,5,2],[1,5,5]]
• Ausgabe: 5
• Erklärung:Wählen Sie Ereignis 2 für eine Summe von 5.

Beispiel 3:

• Eingabe: Ereignisse = [[1,5,3],[1,5,1],[6,6,5]]
• Ausgabe: 8
• Erklärung:Wählen Sie die Ereignisse 0 und 2 für eine Summe von 3 5 = 8.

Einschränkungen:

• 2 <= events.length <= 10⁵
• events[i].length == 3
• 1 <= startTime_i <= endTime_i <= 10⁹
• 1 <= Wert_i <= 10⁶

Hinweis:

1. Wie kann es helfen, die Veranstaltungen nach ihren Startzeiten zu sortieren? Wie wäre es mit der Endzeit?
2. Wie können wir schnell die maximale Punktzahl eines Intervalls erreichen, das sich nicht mit dem von uns gewählten Intervall überschneidet?

Lösung:

Wir können den folgenden Ansatz verwenden:

Ansatz

1. Ereignisse nach Endzeit sortieren:

   • Sortieren hilft uns, mithilfe der binären Suche effizient nicht überlappende Ereignisse zu finden.

2. Binäre Suche nach nicht überlappenden Ereignissen:

   • Verwenden Sie die binäre Suche, um das letzte Ereignis zu finden, das vor der Startzeit des aktuellen Ereignisses endet. Dadurch ist eine Überschneidungsfreiheit gewährleistet.

3. Dynamische Programmierung mit Max Tracking:

   • Behalten Sie beim Durchlaufen der sortierten Ereignisse den maximalen Wert der Ereignisse bis zum aktuellen bei. Dadurch können wir schnell die maximale Summe zweier Ereignisse berechnen.

4. Iterieren und berechnen Sie die maximale Summe:

   • Berechnen Sie für jedes Ereignis die mögliche Summe mit:
     • Nur ​​das aktuelle Ereignis.
     • Das aktuelle Ereignis kombiniert mit dem besten nicht überlappenden Ereignis, das mithilfe der binären Suche gefunden wurde.

Lassen Sie uns diese Lösung in PHP implementieren: 2054. Zwei beste sich nicht überschneidende Veranstaltungen

  
  
  Erläuterung:




Sortieren:


Die Ereignisse sind nach ihrer Endzeit sortiert, was eine effiziente Suche nach dem letzten sich nicht überschneidenden Ereignis ermöglicht.



Binäre Suche:


Für jedes Ereignis ermittelt die binäre Suche das letzte Ereignis, das endet, bevor das aktuelle Ereignis beginnt.



Maximale Nachverfolgung:


Wir pflegen ein Array maxUpTo, das den Maximalwert von Ereignissen bis zum aktuellen Index speichert. Dadurch wird vermieden, dass das Maximum für frühere Indizes neu berechnet wird.



Maximalsummenberechnung:


Berechnen Sie für jedes Ereignis die Summe seines Werts und des besten nicht überlappenden Ereigniswerts. Aktualisieren Sie die globale Höchstsumme entsprechend.





  
  
  Komplexitätsanalyse




Sortierung: O(n log n)


Binäre Suche nach jedem Ereignis: O(log n), n Mal wiederholt → O(n log n)


Insgesamt: O(n log n)



Diese Lösung ist effizient und funktioniert gut innerhalb der Einschränkungen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonZwei beste sich nicht überschneidende Ereignisse. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!