. Mein Kalender II

731. Mein Kalender II

Schwierigkeit:Mittel

Themen: Array, Binäre Suche, Design, Segmentbaum, Präfixsumme, Geordneter Satz

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 Dreifachbuchung führt.

Eine Dreifachbuchung liegt vor, wenn drei Ereignisse einen nicht leeren Schnittpunkt haben (d. h. ein Moment ist allen drei 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 MyCalendarTwo-Klasse:

• MyCalendarTwo() 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 Dreifachbuchung kommt. Andernfalls false zurückgeben und das Ereignis nicht zum Kalender hinzufügen.

Beispiel 1:

• Eingabe:

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

• Ausgabe:

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

• Erklärung:

  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.

Einschränkungen:

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

Hinweis:

1. Speichern Sie zwei sortierte Intervalllisten: Eine Liste enthält alle Zeiten, die mindestens einfach gebucht sind, und eine andere Liste enthält alle Zeiten, die definitiv doppelt gebucht sind. Wenn keine der Doppelbuchungen in Konflikt geraten, ist die Buchung erfolgreich und Sie sollten Ihre Einzel- und Doppelbuchungen entsprechend aktualisieren.

Lösung:

Wir müssen zwei Buchungslisten führen:

1. Einzelbuchungen: Eine Liste, die alle einmal gebuchten Veranstaltungen im Auge behält.
2. Doppelbuchungen: Eine Liste, die alle Veranstaltungen verfolgt, die doppelt gebucht sind.

Wenn eine neue Veranstaltung beantragt wird, müssen wir prüfen, ob diese zu einer Dreifachbuchung führt. Um das zu tun:

• Wir prüfen zunächst, ob sich die neue Veranstaltung mit einem der Intervalle in der Liste Doppelbuchungen überschneidet. Sollte dies der Fall sein, können wir die Veranstaltung nicht hinzufügen, da dies zu einer Dreifachbuchung führen würde.
• Wenn keine Überschneidung mit den Doppelbuchungen vorliegt, prüfen wir anschließend die Einzelbuchungen-Liste und fügen die Überschneidung der neuen Veranstaltung mit bestehenden Veranstaltungen zu den Doppelbuchungen hinzu Liste.

Wenn die Veranstaltung schließlich beide Prüfungen besteht, fügen wir sie der Einzelbuchungsliste hinzu.

Lassen Sie uns diese Lösung in PHP implementieren: 731. Mein Kalender 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";
?>






  
  
  Erläuterung:



Konstruktor (__construct): Initialisiert das Kalenderobjekt mit zwei leeren Arrays, um die Einzelbuchungen und Doppelbuchungen zu speichern.

Buchfunktion (Buch):


Die Funktion übernimmt den Beginn und das Ende eines Ereignisses.
Zunächst wird geprüft, ob sich das Ereignis mit einem Intervall in der doubleBookings-Liste überschneidet. Wenn dies der Fall ist, gibt die Funktion „false“ zurück, da dies zu einer Dreifachbuchung führen würde.
Wenn keine Dreifachbuchung vorliegt, wird die Überschneidung mit Ereignissen in der Liste der Einzelbuchungen überprüft. Jede gefundene Überschneidung wird zur DoubleBookings-Liste hinzugefügt, da es sich nun um eine Doppelbuchung handelt.
Schließlich wird das Ereignis zur SingleBookings-Liste hinzugefügt und die Funktion gibt true zurück.





  
  
  Zeitkomplexität:



Die zeitliche Komplexität beträgt ungefähr O(n) für jeden Buchungsvorgang, wobei n die Anzahl der bisher getätigten Buchungen ist. Dies liegt daran, dass wir für jede Buchung möglicherweise alle vorherigen Buchungen sowohl in der SingleBookings- als auch in der DoubleBookings-Liste überprüfen müssen.


Diese Lösung verarbeitet effizient bis zu 1000 Aufrufe der Buchfunktion, je nach den Problembeschrä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 von. Mein Kalender II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!