Deux meilleurs événements sans chevauchement

2054. Deux meilleurs événements sans chevauchement

Difficulté :Moyen

Sujets : Tableau, recherche binaire, programmation dynamique, tri, tas (file d'attente prioritaire)

Vous recevez un indexé 0 tableau d'événements entiers 2D où events[i] = [startTime_i, endTime_i, value _je]. Le i^ème événement commence à startTime_i et se termine à endTime_i, et si vous assistez à cet événement, vous recevrez une valeur de value_i . Vous pouvez choisir au plus deux événements qui ne se chevauchent pas auxquels assister de telle sorte que la somme de leurs valeurs soit maximisée.

Renvoyer cette somme maximale.

Notez que l'heure de début et l'heure de fin sont inclusives : c'est-à-dire que vous ne pouvez pas assister à deux événements dont l'un commence et l'autre se termine en même temps. Plus précisément, si vous assistez à un événement avec une heure de fin t, le prochain événement doit commencer à ou après t 1.

Exemple 1 :

• Entrée : événements = [[1,3,2],[4,5,2],[2,4,3]]
• Sortie : 4
• Explication : Choisissez les événements verts, 0 et 1 pour une somme de 2 2 = 4.

Exemple 2 :

• Entrée : événements = [[1,3,2],[4,5,2],[1,5,5]]
• Sortie : 5
• Explication : Choisissez l'événement 2 pour une somme de 5.

Exemple 3 :

• Entrée : événements = [[1,5,3],[1,5,1],[6,6,5]]
• Sortie : 8
• Explication : Choisissez les événements 0 et 2 pour une somme de 3 5 = 8.

Contraintes :

• 2 5
• événements[i].length == 3
• 1 i i 9
• 1 i 6

Indice :

1. En quoi le tri des événements en fonction de leurs heures de début peut-il aider ? Et la fin des temps ?
2. Comment pouvons-nous obtenir rapidement le score maximum d'un intervalle ne croisant pas l'intervalle que nous avons choisi ?

Solution :

Nous pouvons utiliser l'approche suivante :

Approche

1. Trier les événements par heure de fin :

   • Le tri nous aide à trouver efficacement des événements qui ne se chevauchent pas à l'aide de la recherche binaire.

2. Recherche binaire d'événements qui ne se chevauchent pas :

   • Utilisez la recherche binaire pour trouver le dernier événement qui se termine avant l'heure de début de l'événement en cours. Cela garantit le non-chevauchement.

3. Programmation dynamique avec suivi maximum :

   • Lorsque vous parcourez les événements triés, conservez la valeur maximale des événements jusqu'à celui en cours. Cela nous permet de calculer rapidement la somme maximale de deux événements.

4. Itérer et calculer la somme maximale :

   • Pour chaque événement, calculez la somme possible en utilisant :
     • Uniquement l'événement en cours.
     • L'événement en cours combiné avec le meilleur événement sans chevauchement trouvé à l'aide de la recherche binaire.

Implémentons cette solution en PHP : 2054. Deux meilleurs événements sans chevauchement

<?php /**
 * @param Integer[][] $events
 * @return Integer
 */
function maxTwoEvents($events) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage:
$events1 = [[1, 3, 2], [4, 5, 2], [2, 4, 3]];
$events2 = [[1, 3, 2], [4, 5, 2], [1, 5, 5]];
$events3 = [[1, 5, 3], [1, 5, 1], [6, 6, 5]];

echo maxTwoEvents($events1) . "\n"; // Output: 4
echo maxTwoEvents($events2) . "\n"; // Output: 5
echo maxTwoEvents($events3) . "\n"; // Output: 8
?>

Explication:

1. Tri :

   • Les événements sont triés selon leur heure de fin, ce qui permet une recherche efficace du dernier événement qui ne se chevauche pas.

2. Recherche binaire :

   • Pour chaque événement, la recherche binaire détermine le dernier événement qui se termine avant le début de l'événement en cours.

3. Suivi maximum :

   • Nous maintenons un tableau maxUpTo, qui stocke la valeur maximale des événements jusqu'à l'index actuel. Cela évite de recalculer le maximum pour les indices antérieurs.

4. Calcul de la somme maximale :

   • Pour chaque événement, calculez la somme de sa valeur et de la meilleure valeur d'événement sans chevauchement. Mettez à jour la somme maximale globale en conséquence.

Analyse de complexité

• Tri : O(n log n)
• Recherche binaire pour chaque événement : O(log n), répété n fois → O(n log n)
• Global : O(n log n)

Cette solution est efficace et fonctionne bien dans les limites des contraintes.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du 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!