Algorithmus entwerfen, der die Uhrzeit bestimmt, zu der gleichzeitig am meisten Personen anwesend waren

Question

Aufgabe:

In einer Einkaufsgalerie werden Daten erhoben, wann Personen diese betreten und verlassen haben. Die Daten haben für jede der insgesamt n an diesem Tag erfassten Personen die Form [ai, bi[ (0 ≤ i < n) mit ai < bi, was bedeutet, dass die Person i zum Zeitpunkt ai die Galerie betritt und zum Zeitpunkt bi gerade eben die Galerie verlassen hat. Basierend auf diesen Daten soll eine Uhrzeit gefunden werden, bei der maximal viele Personen in der Galerie waren.

Nun sollen wir einen Algorithmus entwerfen, der die Uhrzeit bestimmt, zu der gleichzeitig am meisten Personen anwesend waren. Dieser bzw. dessen Laufzeit darf jedoch lediglich von der Personenanzahl n und nicht von dem maximal auftrenden Zeitpunkt abhängen.

Answer 1

Antwort mit KI erzeugt

Lösungsansatz:

Wir können das Problem lösen, indem wir eine Liste von Ereignissen erstellen, bei denen jede Person die Galerie betritt und verlässt. Anstatt die Uhrzeit zu speichern, wird jede Liste als ein Paar von Ereignissen gespeichert: Das Betreten der Person wird als positives Ereignis (+1) und das Verlassen als negatives Ereignis (-1) betrachtet.

Dieser Ansatz ermöglicht es uns, effizient die Zeitpunkte zu finden, zu denen die meisten Personen anwesend waren, indem wir die Ereignisse in chronologischer Reihenfolge durchlaufen und eine laufende Summe der Anwesenheiten berechnen. Wir speichern den Höchstwert der Anwesenheit sowie die dazugehörige(n) Zeit(en), um schlussendlich den oder die Zeitpunkte zu ermitteln, an denen die Galerie die höchste Besucheranzahl verzeichnete.

Algorithmus:

1. Erstelle eine leere Liste von Ereignissen.
2. Füge für jede Person zwei Ereignisse hinzu: Ein Ereignis für das Betreten (+1) der Galerie und eines für das Verlassen (-1) der Galerie, jeweils mit dem entsprechenden Zeitpunkt als Schlüssel.
3. Sortiere die Ereignisliste nach Zeitpunkten. Wenn zwei Ereignisse denselben Zeitpunkt haben, ordne das Betreten (+1) vor dem Verlassen (-1), um korrekt zu zählen, dass Personen, die zur gleichen Zeit ankommen und gehen, als anwesend gezählt werden.
4. Initialisiere eine Variable für die laufende Summe der Anwesenheiten (aktuelleAnzahl) und eine Variable für die maximale Anzahl der Anwesenheiten (maxAnzahl). Erstelle eine leere Liste für die Zeitpunkte mit maximaler Anwesenheit (maxZeiten).
5. Durchlaufe die sortierte Ereignisliste:
- Aktualisiere aktuelleAnzahl basierend auf dem Ereignistyp (+1 für Betreten, -1 für Verlassen).
- Wenn aktuelleAnzahl größer als maxAnzahl ist:
- Setze maxAnzahl auf aktuelleAnzahl.
- Leere maxZeiten und füge den aktuellen Zeitpunkt hinzu.
- Wenn aktuelleAnzahl gleich maxAnzahl ist:
- Füge den aktuellen Zeitpunkt zu maxZeiten hinzu, falls dies noch nicht geschehen ist.
6. Die Zeitpunkte in der Liste maxZeiten entsprechen den Zeiten, zu denen die meisten Personen anwesend waren.

Python-Implementierung:

python
def findeMaximaleAnwesenheit(ereignisse):
    # Schritt 1 & 2: Erstellen einer Ereignisliste
    flat_ereignisse = []
    for start, ende in ereignisse:
        flat_ereignisse.append((start, 1))  # Betreten
        flat_ereignisse.append((ende, -1))  # Verlassen
      
    # Schritt 3: Sortieren der Ereignisse
    flat_ereignisse.sort(key=lambda x: (x[0], x[1]))
    
    aktuelleAnzahl = 0
    maxAnzahl = 0
    maxZeiten = []
    
    # Schritt 5: Durchlaufen der Ereignisliste
    for zeitpunkt, ereignis in flat_ereignisse:
        aktuelleAnzahl += ereignis
        if aktuelleAnzahl > maxAnzahl:
            maxAnzahl = aktuelleAnzahl
            maxZeiten = [zeitpunkt]
        elif aktuelleAnzahl == maxAnzahl and (not maxZeiten or zeitpunkt > maxZeiten[-1]):
            maxZeiten.append(zeitpunkt)
    
    return maxZeiten, maxAnzahl

# Beispiel
ereignisse = [(1, 3), (2, 5), (4, 6)]
maxZeiten, maxAnzahl = findeMaximaleAnwesenheit(ereignisse)
print("Maximale Anwesenheit:", maxAnzahl, "zu den Zeiten:", maxZeiten)

Dieser Algorithmus garantiert, dass die Laufzeit primär von der Anzahl der Personen \(n\) abhängt und effizient die gesuchten Zeitpunkte findet.