Maison > Article > développement back-end > . 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 :
Exemple 1 :
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
[null, true, true, true, false, true, true]
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 :
Indice :
Solution :
Nous devons maintenir deux listes de réservations :
Lorsqu'un nouvel événement est demandé, nous devons vérifier s'il entraînera une triple réservation. Pour ce faire :
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 :
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 :
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!