Beschreiben Sie die Aufgabe, benachbarte Zahlen in Bereiche zusammenzufassen.

Die Aufgabe, benachbarte Zahlen zu Bereichen zusammenzufassen, besteht darin, die minimale Anzahl an zusammenhängenden Intervallen (Bereichen) zu bilden, die alle diese Zahlen ohne Lücken abdecken.

Zum Beispiel gibt es Zahlen: [1, 2, 3, 5, 6, 8]

Ergebnis der Zusammenfassung:

• [1-3]
• [5-6]
• [8]

Dies ist nützlich, um die Speicherung oder Anzeige von Daten zu optimieren, wenn aufeinanderfolgende Zahlen kompakt als Bereich dargestellt werden können.

Hauptschritte der Lösung:

1. Array der Zahlen sortieren.
2. Über die sortierte Liste iterieren und den aktuellen Bereich bilden.
3. Wenn das nächste Element benachbart ist (aktuell + 1), den Bereich erweitern.
4. Wenn nicht, den aktuellen Bereich speichern und einen neuen beginnen.

Die Komplexität des Algorithmus ist — O(n log n) aufgrund der Sortierung, wobei n die Anzahl der Zahlen ist.

Beispiel in Python:

def collapse_ranges(nums):
    if not nums:
        return []
    nums = sorted(set(nums))
    ranges = []
    start = prev = nums[0]
    for num in nums[1:]:
        if num == prev + 1:
            prev = num
        else:
            ranges.append((start, prev))
            start = prev = num
    ranges.append((start, prev))
    return ranges

# Beispiel
print(collapse_ranges([1,2,3,5,6,8]))  # [(1,3), (5,6), (8,8)]