. Mein Kalender I

729. Mein Kalender I

Schwierigkeit:Mittel

Themen: Array, Binäre Suche, Design, Segmentbaum, geordnete Menge

Sie implementieren ein Programm, das Sie als Kalender verwenden möchten. Wir können eine neue Veranstaltung hinzufügen, wenn das Hinzufügen der Veranstaltung nicht zu einer Doppelbuchung führt.

Eine Doppelbuchung tritt auf, wenn zwei Ereignisse einen nicht leeren Schnittpunkt haben (d. h. ein Moment ist beiden Ereignissen gemeinsam).

Das Ereignis kann als Paar aus ganzen Zahlen Anfang und Ende dargestellt werden, das eine Buchung im halboffenen Intervall [Anfang, Ende] darstellt, dem Bereich reeller Zahlen x, so dass Anfang <= x < Ende.

Implementieren Sie die MyCalendar-Klasse:

• MyCalendar() Initialisiert das Kalenderobjekt.
• boolean book(int start, int end) Gibt true zurück, wenn das Ereignis erfolgreich zum Kalender hinzugefügt werden kann, ohne dass es zu einer Doppelbuchung kommt. Andernfalls geben Sie false zurück und fügen Sie das Ereignis nicht zum Kalender hinzu.

Beispiel 1:

• Eingabe:

  ["MyCalendar", "book", "book", "book"]
  [[], [10, 20], [15, 25], [20, 30]]

• Ausgabe:

  [null, true, false, true]

• Erklärung:

  MyCalendar myCalendar = new MyCalendar();
  myCalendar.book(10, 20); // return True
  myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
  myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Einschränkungen:

• 0 <= Start < Ende <= 10⁹
• Es werden höchstens 1000 Anrufe zur Buchung getätigt.

Hinweis:

1. Speichern Sie die Ereignisse als sortierte Liste von Intervallen. Wenn keines der Ereignisse in Konflikt steht, kann das neue Ereignis hinzugefügt werden.

Lösung:

Wir müssen jede Veranstaltung speichern und prüfen, ob die neue Veranstaltung mit einer der bestehenden Veranstaltungen in Konflikt steht, bevor wir sie buchen. Da maximal 1000 Buchungsaufrufe zulässig sind, können wir die Veranstaltungen in einer Liste speichern und sie durchlaufen, um bei der Buchung neuer Veranstaltungen auf Überschneidungen zu prüfen.

Planen:

1. Ereignisse speichern: Wir führen eine Liste, in der jeder Eintrag ein Paar [Anfang, Ende] ist, das die gebuchten Zeitintervalle darstellt.
2. Auf Konflikte prüfen: Bevor wir eine neue Veranstaltung hinzufügen, gehen wir die Liste der gebuchten Veranstaltungen durch und prüfen, ob die neue Veranstaltung mit einer bestehenden Veranstaltung in Konflikt steht. Eine Überschneidung liegt vor, wenn die Startzeit des neuen Ereignisses kleiner ist als die Endzeit eines bestehenden Ereignisses und die Endzeit des neuen Ereignisses größer ist als die Startzeit eines bestehenden Ereignisses.
3. Veranstaltung buchen: Wenn keine Konflikte gefunden werden, fügen wir die neue Veranstaltung unserer Buchungsliste hinzu.

Lassen Sie uns diese Lösung in PHP implementieren: 729. Mein Kalender I

book($start, $end);
 */

// Example Usage:
$myCalendar = new MyCalendar();
var_dump($myCalendar->book(10, 20)); // true, no conflicts, booking added
var_dump($myCalendar->book(15, 25)); // false, conflict with [10, 20]
var_dump($myCalendar->book(20, 30)); // true, no conflicts, booking added
?>






  
  
  Erläuterung:



Konstruktor (__construct): Initialisiert ein leeres Array $events, um alle gebuchten Ereignisse im Auge zu behalten.

Buchungsfunktion (Buch):


Es ist der Beginn und das Ende eines neuen Ereignisses.
Es durchläuft die Liste der zuvor gebuchten Veranstaltungen und prüft auf etwaige Überschneidungen:


Eine Überschneidung tritt auf, wenn die neue Veranstaltung beginnt, bevor eine bestehende Veranstaltung endet ($start < $bookedEnd) und endet, nachdem eine bestehende Veranstaltung beginnt ($end > $bookedStart).


Wenn eine Überschneidung festgestellt wird, gibt die Funktion „false“ zurück, was bedeutet, dass die Veranstaltung nicht gebucht werden kann.
Wenn keine Konflikte gefunden werden, wird das Ereignis zum Array $events hinzugefügt und die Funktion gibt „true“ zurück, um eine erfolgreiche Buchung anzuzeigen.





  
  
  Zeitkomplexität:




Eine Veranstaltung buchen: Bei jedem Buchungsaufruf wird die neue Veranstaltung mit allen zuvor gebuchten Veranstaltungen verglichen. Dies führt zu einer zeitlichen Komplexität von O(n) für jeden Buchungsvorgang, wobei n die Anzahl der zuvor gebuchten Veranstaltungen ist.

Raumkomplexität: Die Raumkomplexität beträgt O(n), da wir bis zu n Ereignisse im Array speichern.



  
  
  Beispielhafte Vorgehensweise:




Erste Buchung (Buch(10, 20)):


Keine vorherigen Veranstaltungen, daher ist die Veranstaltung [10, 20] erfolgreich gebucht.
Ausgabe: wahr




Zweite Buchung (Buch(15, 25)):


Das neue Ereignis [15, 25] steht in Konflikt mit dem zuvor gebuchten Ereignis [10, 20], da es eine Überschneidung im Zeitintervall gibt (15 liegt zwischen 10 und 20).
Ausgabe: falsch




Dritte Buchung (Buch(20, 30)):


Das neue Ereignis [20, 30] überschneidet sich nicht mit [10, 20], da die Startzeit des neuen Ereignisses genau mit dem Ende des ersten Ereignisses übereinstimmt (keine Überlappung, da es sich um ein halboffenes Intervall handelt).
Ausgabe: wahr





Dieser einfache Ansatz verarbeitet effizient bis zu 1000 Ereignisse und sorgt gleichzeitig für Klarheit und Korrektheit.

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 von. Mein Kalender I. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!