Lösung algorithmischer Probleme: die Möglichkeit, ein Hotel zu buchen

Die Übersetzung des Artikels wurde speziell für Studenten des Kurses "Algorithmen für Entwickler" vorbereitet.



Dieser Artikel ist Teil einer Reihe zur Lösung algorithmischer Probleme. Aufgrund meiner persönlichen Erfahrung stellte ich fest, dass die meisten Ressourcen die Lösung einfach im Detail beschreiben. Eine Erklärung der Hauptargumentation, die es ermöglicht, eine wirksame Lösung zu finden, ist leider nicht sehr verbreitet. Ziel dieser Reihe ist es daher, den möglichen Denkweg für die Lösung von Problemen von Grund auf zu beschreiben.

---

Herausforderung

• Aufgabe: InterviewBit

Der Hotelmanager muss N Reservierungsaufträge für die nächste Saison bearbeiten. Sein Hotel verfügt über K Zimmer. Die Buchungsinformationen enthalten das Check-in-Datum und das Check-out-Datum. Der Manager möchte herausfinden, ob im Hotel genügend Zimmer vorhanden sind, um die Nachfrage zu befriedigen.

Eingabedaten:

- Der erste, der eine Liste mit Informationen zur Ankunftszeit eingibt
- Zweitens - eine Liste mit Informationen zum Zeitpunkt der Abreise
- Dritter - K, der die Anzahl der Räume angibt

Ausgabedaten:
- Ein logischer Wert, der die Möglichkeit angibt, Zimmer zu buchen
false bedeutet, dass das Hotel nicht genügend Zimmer für N Buchungen hat
true bedeutet, dass das Hotel über genügend Zimmer für N Buchungen verfügt

Ein Beispiel:

Eingabedaten:
- Check-in = [1, 3, 5]
- Abfahrt = [2, 6, 10]
- K = 1

Ausgabe: false. Am Tag = 5 hat das Hotel 2 Gäste. Wir haben aber nur eine Nummer.

• Kategorie: Arrays

Entscheidungsprozess

Diese Aufgabe ist meiner Meinung nach interessant, da es viele verschiedene Möglichkeiten gibt, sie zu lösen. Schauen wir uns die Optionen an.

Eine Struktur, in der Zähler für jeden Tag gespeichert werden
Die erste Idee könnte sein, dass wir eine Struktur benötigen, um die Anzahl der Bestellungen für jeden Tag zu speichern. Diese Struktur kann ein Array mit einer festen Größe sein (bestimmt durch den maximalen Abreisetag).

Eingabedaten:
- Einträge = [1, 3, 5]
- Abfahrten = [2, 6, 10]
- k = 1

In diesem Beispiel beträgt die Größe des Arrays 10 (da der letzte Exit am 10. Tag erfolgt). Um dieses Array zu füllen, gehen wir die Listen der Ein- und Ausgänge durch und erhöhen oder verringern den Zähler des entsprechenden Tages. Pseudocode-Beispiel:

int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- } 

Als Ergebnis erhalten wir das folgende Array:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Nachdem das Array voll ist, müssen Sie es nur noch durchgehen und prüfen, ob alle Elemente k (Anzahl der Räume) nicht überschreiten.

Im vorherigen Beispiel war die maximale Anzahl von Zimmern 1. Da wir an Tag 5 2 Reservierungen haben, geben wir false .

Die zeitliche Komplexität dieser Lösung ist O (n), wobei n die Anzahl der Reservierungen ist, und räumlich ist O (m), wobei m der maximale Abreisetag ist. Theoretisch nicht schlecht, aber es wird wahrscheinlich viel Speicher für ein großes Array reserviert, obwohl das meiste davon nicht verwendet wird.

Zum Beispiel:

Eingabedaten:
- Einträge = [1, 3, 5]
- Abfahrten = [2, 10000, 10]
- k = 1

In diesem Fall wird ein Array von 10 Tausend Ganzzahlen zugewiesen.

Schauen wir uns andere Lösungen an.

Speicher für Ereignissammlungen

Welche anderen Möglichkeiten gibt es? Schauen wir uns noch einmal an, was mit der vorherigen Struktur passiert ist:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Wir sehen, dass einige Informationen dupliziert werden. Beispielsweise ändert sich zwischen 6 und 9 Tagen die Anzahl der Buchungen nicht, da wir wissen, dass in diesem Zeitraum nichts passieren wird.

Könnte es besser sein, wenn stattdessen Ereignisse gespeichert werden? Nehmen wir noch einmal das gleiche Beispiel:

Eingabedaten:
- Einträge = [1, 3, 5]
- Abfahrten = [2, 6, 10]
Tag 1: +1 Buchung
Tag 2: -1 Buchung
Tag 3: +1 Buchung
Tag 6: -1 Buchung
Tag 5: +1 Buchung
Tag 10: -1 Buchung

Die Lösung besteht darin, diese Ereignisse zu durchlaufen, um den Zähler zu erhöhen oder zu verringern. Wenn der Zähler irgendwann größer als k , geben wir false . Zum Durchlaufen muss diese Sammlung von Ereignissen jedoch sortiert werden.

Welche Struktur ist hier besser zu verwenden? Fassen wir unsere Anforderungen zusammen:

• Suchen Sie, um zu überprüfen, ob ein solcher Tag bereits existiert
• Einen neuen Tag hinzufügen,
• Struktur anzeigen, um über jeden sortierten Tag zu iterieren.

Wie wäre es mit einem binären Suchbaum (BST)?

Jeder Knoten kann wie folgt dargestellt werden:

 class Node { int day int count Node left Node right } 

Die Sortierung erfolgt im Tagesfeld.

Betrachten wir die Konsequenzen in Bezug auf die zeitliche Komplexität:

• Suchen Sie, um zu überprüfen, ob ein solcher Tag bereits existiert: O (log (n)) im Durchschnitt, O (n) im schlimmsten Fall,
• Hinzufügen eines neuen Tages: O (log (n)) im Durchschnitt, O (n) im schlimmsten Fall,
• Zeigen Sie die Struktur für die Iteration über jeden sortierten Tag an: O (n) mithilfe einer Tiefensuche.

Da wir jedes Element durchlaufen und in den Baum einfügen müssen, beträgt die Komplexität des Algorithmus im Durchschnitt O (n log (n)), im schlechtesten Fall O (n²).

Eine andere Möglichkeit besteht darin, eine Hash-Tabelle zu verwenden und die Schlüssel zu sortieren, nachdem alle Ereignisse hinzugefügt wurden:

• Suchen Sie, um zu überprüfen, ob ein solcher Tag bereits existiert: O (1) im Durchschnitt, O (n) im schlimmsten Fall (die Wahrscheinlichkeit hängt von der Kapazität des assoziativen Arrays ab),
• Hinzufügen eines neuen Tages: O (1) im Durchschnitt, O (n) im schlimmsten Fall,
• Zeigen Sie die Struktur für die Iteration über jeden sortierten Tag an: O (n log (n)) zum Sortieren von Schlüsseln und O (n) zum Sortieren.

Am Ende hat die Lösung im mittleren Fall (aufgrund der Sortieroperation) O (n log (n)) und im schlimmsten Fall O (n²). Diese Lösung scheint dieselbe Komplexität zu haben wie eine baumbasierte Lösung.

Schauen wir uns eine mögliche Implementierung in Java mit einem sortierten assoziativen Array an:

 public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { //   Map<Integer, Integer> events = new HashMap<>(); //   int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); //      Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); //      current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } //    Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); //  count     if (count > k) { return false; } } return true; } 

Konstante räumliche Komplexität

Wenn wir unseren Algorithmus optimieren wollen, müssen wir uns überlegen, ob es wirklich notwendig ist, alle diese Ereignisse zu speichern. Können wir nicht einfach die Erfassungsdaten (Ein- und Ausgänge) sortieren und dabei das Reservierungslimit überprüfen?

Eine Lösung ist möglich, aber dafür wäre es notwendig, die Eingabe durch vorheriges Sortieren zu vereinfachen.

Wenn beide Sammlungen sortiert sind, können wir einfach mit zwei Zeigern (einer für Eingänge und einer für Ausgänge) über jedes Element iterieren und die Einschränkungen im laufenden Betrieb überprüfen.

Wie Sie sehen, müssen wir bei jeder Iteration noch das Minimum zwischen arrivals.get(indexArrival) departures.get(indexDeparture) , um herauszufinden, welcher Zeiger aktualisiert werden muss.

Im Allgemeinen weist der Algorithmus aufgrund von Sortieroperationen eine konstante zeitliche und räumliche Komplexität O (n log (n)) auf.