. Mon calendrier II

731. Mon calendrier II

Difficulté :Moyen

Sujets : Tableau, recherche binaire, conception, arbre de segments, somme de préfixes, ensemble ordonné

Vous mettez en œuvre un programme à utiliser comme calendrier. Nous pouvons ajouter un nouvel événement si l'ajout de l'événement n'entraîne pas une triple réservation.

Une triple réservation se produit lorsque trois événements ont une intersection non vide (c'est-à-dire qu'un moment est commun aux trois événements.).

L'événement peut être représenté comme une paire d'entiers début et fin qui représente une réservation sur l'intervalle semi-ouvert [début, fin), la plage de nombres réels x tels que start <= x < fin.

Implémentez la classe MyCalendarTwo :

• MyCalendarTwo() Initialise l'objet calendrier.
• boolean book(int start, int end) Renvoie true si l'événement peut être ajouté au calendrier avec succès sans provoquer une triple réservation. Sinon, renvoyer false et ne pas ajouter l'événement au calendrier.

Exemple 1 :

• Entrée :

  ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
  [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

• Sortie :

  [null, true, true, true, false, true, true]

• Explication :

  MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
  myCalendarTwo.book(10, 20); // return True, The event can be booked.
  myCalendarTwo.book(50, 60); // return True, The event can be booked.
  myCalendarTwo.book(10, 40); // return True, The event can be double booked.
  myCalendarTwo.book(5, 15);  // return False, The event cannot be booked, because it would result in a triple booking.
  myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
  myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Contraintes :

• 0 <= début < fin <= 10⁹
• Au maximum 1000 appels seront effectués pour réserver.

Indice :

1. Stockez deux listes triées d'intervalles : une liste contiendra toutes les heures qui sont au moins réservées en une seule fois, et une autre liste sera toutes les heures qui sont définitivement réservées en double. Si aucune des réservations doubles n'est en conflit, la réservation réussira et vous devez mettre à jour vos réservations simples et doubles en conséquence.

Solution :

Nous devons maintenir deux listes de réservations :

1. Réservations uniques : une liste qui garde une trace de tous les événements réservés une fois.
2. Réservations doubles : une liste qui garde une trace de tous les événements qui font l'objet d'une double réservation.

Lorsqu'un nouvel événement est demandé, nous devons vérifier s'il entraînera une triple réservation. Pour ce faire :

• Nous vérifions d'abord si le nouvel événement chevauche l'un des intervalles de la liste des réservations doubles. Si c'est le cas, nous ne pouvons pas ajouter l'événement car cela entraînerait une triple réservation.
• S'il n'y a pas de chevauchement avec les réservations doubles, nous vérifions alors la liste des réservations simples et ajoutons le chevauchement du nouvel événement avec les événements existants aux réservations doubles liste.

Enfin, si l'événement réussit les deux contrôles, nous l'ajoutons à la liste des réservations uniques.

Implémentons cette solution en PHP : 731. Mon calendrier II

book($start, $end);
 */


// Example Usage
$calendar = new MyCalendarTwo();
echo $calendar->book(10, 20) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(50, 60) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(10, 40) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(5, 15) ? 'true' : 'false'; // false
echo "\n";
echo $calendar->book(5, 10) ? 'true' : 'false'; // true
echo "\n";
echo $calendar->book(25, 55) ? 'true' : 'false'; // true
echo "\n";
?>






  
  
  Explication:



Constructeur (__construct) : Initialise l'objet calendrier avec deux tableaux vides pour stocker les réservations simples et les réservations doubles.

Fonction Livre (livre) :


La fonction prend le début et la fin d'un événement.
Il vérifie d'abord si l'événement chevauche un intervalle de la liste doubleBookings. Si c'est le cas, la fonction renvoie false car cela entraînerait une triple réservation.
S'il n'y a pas de triple réservation, il vérifie le chevauchement avec les événements de la liste des réservations simples. Tout chevauchement trouvé est ajouté à la liste des doubles réservations, car il représente désormais une double réservation.
Enfin, l'événement est ajouté à la liste singleBookings et la fonction renvoie true.





  
  
  Complexité temporelle :



La complexité temporelle est d'environ O(n) pour chaque opération de réservation, où n est le nombre de réservations effectuées jusqu'à présent. En effet, pour chaque réservation, nous devrons peut-être vérifier toutes les réservations précédentes dans les listes singleBookings et doubleBookings.


Cette solution gère efficacement jusqu'à 1 000 appels à la fonction book selon les contraintes du problème.

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!