2025_05.md

Tag 05 - Intervall-Merge und Bereichsprüfung

Aufgabe

Gegeben sind Zahlenbereiche ("frisch") und einzelne Zahlen ("Zutaten"):

• Teil 1: Wie viele Zutaten liegen in den frischen Bereichen?
• Teil 2: Wie viele Zahlen sind insgesamt in den frischen Bereichen enthalten?

Lösung

Eingabeformat

Zwei Arten von Zeilen:

• Bereiche: start-ende (z.B. 10-20)
• Einzelne Zutaten: Einzelne Zahl (z.B. 15)
• Leere Zeilen: Werden ignoriert

Beispiel:

10-20
5-8
15
25
30-35

Algorithmus

Der Algorithmus besteht aus drei Hauptschritten:

1. Eingabe parsen

def eingabe_parsen():
    frisch = set()
    zutaten = set()
    for zeile in aufgabe.zeilen:
        zeile = zeile.strip()
        if "-" in zeile:
            start, ende = map(int, zeile.split("-"))
            frisch.add((start, ende))
            continue
        if zeile == "":
            continue
        zutaten.add(int(zeile))
    aufgabe.frisch = sorted(frisch)
    aufgabe.zutaten = sorted(zutaten)

Logik:

• Zeilen mit -: Bereich → Parse als Tuple (start, ende)
• Leere Zeilen: Ignorieren
• Andere Zeilen: Einzelne Zutat → Parse als Integer
• Sets: Automatische Duplikat-Entfernung
• Sortierung: Wichtig für nächsten Schritt!

2. Bereiche zusammenführen (Merge)

def kumuliere_frische_bereiche():
    bereiche = []
    aktuelle_start, aktuelles_ende = aufgabe.frisch[0]
    for i, (start, ende) in enumerate(aufgabe.frisch[1:]):
        if start <= aktuelles_ende + 1:
            aktuelles_ende = max(aktuelles_ende, ende)
        else:
            bereiche.append((aktuelle_start, aktuelles_ende))
            aktuelle_start, aktuelles_ende = start, ende
    bereiche.append((aktuelle_start, aktuelles_ende))
    aufgabe.frisch = bereiche

Interval-Merge-Algorithmus:

Initialisierung:

• Starte mit dem ersten Bereich als "aktueller Bereich"

Für jeden folgenden Bereich:

1. Prüfe Überlappung oder direkte Angrenzung:

   if start <= aktuelles_ende + 1:

   • start <= aktuelles_ende: Überlappung
   • start == aktuelles_ende + 1: Direkt angrenzend

2. Fall A: Überlappung/Angrenzung:

   aktuelles_ende = max(aktuelles_ende, ende)

   • Erweitere den aktuellen Bereich bis zum Maximum der beiden Enden
   • Der Bereich wird nicht zur Liste hinzugefügt (wird weiter gemerged)

3. Fall B: Keine Verbindung:

   bereiche.append((aktuelle_start, aktuelles_ende))
   aktuelle_start, aktuelles_ende = start, ende

   • Speichere den bisherigen Bereich
   • Starte neuen aktuellen Bereich

Abschluss:

• Füge letzten Bereich hinzu (wird in Schleife nie hinzugefügt)

Beispiel:

Eingabe (sortiert): [(5, 8), (10, 20), (15, 25), (30, 35)]

Schritt 1: Aktuell = (5, 8)
Schritt 2: (10, 20) - 10 > 9 → Speichere (5, 8), Aktuell = (10, 20)
Schritt 3: (15, 25) - 15 <= 20 → Merge, Aktuell = (10, 25)
Schritt 4: (30, 35) - 30 > 26 → Speichere (10, 25), Aktuell = (30, 35)
Abschluss: Speichere (30, 35)

Ergebnis: [(5, 8), (10, 25), (30, 35)]

3. Aufgabe 1 - Zutaten in Bereichen zählen

def aufgabe1():
    for zutat in aufgabe.zutaten:
        for start, ende in aufgabe.frisch:
            if start <= zutat <= ende:
                aufgabe.loesung1 += 1
                break

Logik:

• Für jede Zutat: Prüfe alle Bereiche
• Wenn Zutat im Bereich liegt: Zähle und breche ab
• Break wichtig: Eine Zutat kann nur einmal gezählt werden

Optimierung durch Merge:

• Ohne Merge: Mehrere überlappende Bereiche müssten geprüft werden
• Mit Merge: Bereiche sind disjunkt, einfachere Prüfung

4. Aufgabe 2 - Gesamtzahl in Bereichen

def aufgabe2():
    for start, ende in aufgabe.frisch:
        aufgabe.loesung2 += (ende - start + 1)

Logik:

• Für jeden Bereich: Anzahl der enthaltenen Zahlen = ende - start + 1
• +1 wichtig: Bereich ist inklusiv

Beispiel:

• Bereich (10, 20) enthält: 10, 11, ..., 20 → 11 Zahlen
• Formel: 20 - 10 + 1 = 11 ✓

Warum Merge notwendig:

• Ohne Merge würden überlappende Bereiche Zahlen mehrfach zählen!
• Merge garantiert: Jede Zahl wird maximal einmal gezählt

Komplexität

Parsing:

• Zeit: O(n) wobei n = Anzahl Zeilen
• Platz: O(n) für Sets

Merge:

• Zeit: O(m log m) wobei m = Anzahl Bereiche (Sortierung dominiert)
• Platz: O(m) für Ergebnis-Liste

Aufgabe 1:

• Zeit: O(z * m) wobei z = Anzahl Zutaten
• Schlechtester Fall: Jede Zutat wird mit allen Bereichen verglichen

Aufgabe 2:

• Zeit: O(m)
• Einfache Summierung

Gesamt:

• Zeit: O(n + m log m + z * m)
• Platz: O(n + m)

Besonderheiten

Intervall-Merge:

• Klassischer Greedy-Algorithmus
• Erfordert sortierte Eingabe
• Berücksichtigt auch direkt angrenzende Bereiche (+1)

Set-Verwendung:

• Automatische Duplikat-Entfernung
• Effiziente Membership-Tests

Inklusive Bereiche:

• Beide Grenzen sind Teil des Bereichs
• ende - start + 1 für Anzahl

Angrenzende Bereiche:

• [10, 15] und [16, 20] werden zu [10, 20] gemerged
• Bedingung: start <= aktuelles_ende + 1

Alternative: V2-Version (2025_15.py)

Eine kompaktere Version existiert in 2025_15.py, die:

• Alle Schritte in einer Funktion vereint
• Inline-Berechnungen verwendet
• Weniger Funktionsaufrufe hat
• Denselben Algorithmus implementiert (nur kompakter)