Popíšte úlohu zoskupovania susedných čísel do rozsahov.

Úloha spájania susedných čísel do rozsahov spočíva v tvorbe čo najmenšieho počtu súvislých intervalov (rozsahov), ktoré pokryjú všetky tieto čísla bez medzier.

Napríklad, sú čísla: [1, 2, 3, 5, 6, 8]

Výsledok spájania:

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

Toto je užitočné na optimalizáciu ukladania alebo zobrazovania údajov, keď je možné sekvenčné čísla kompaktné reprezentovať ako rozsah.

Hlavné kroky riešenia:

1. Usporiadať pole čísel.
2. Iterovať cez zoradený zoznam a tvoriť aktuálny rozsah.
3. Ak je nasledujúci prvok susedný (aktuálny + 1), rozšíriť rozsah.
4. Ak nie, uložiť aktuálny rozsah a začať nový.

Zložitosť algoritmu je — O(n log n) kvôli zoradeniu, kde n je počet čísel.

Príklad v Pythone:

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

# Príklad
print(collapse_ranges([1,2,3,5,6,8]))  # [(1,3), (5,6), (8,8)]