Kirjeldage ülesannet naabersuhete arvude rühmitamiseks vahemikeks.

Järgnevate arvude ühendamise ülesanne seisneb selles, et moodustada minimaalne arv järjestikuseid vahemikke (diapasone), mis katavad kõik need arvud ilma vahepealsete tühikuteta.

Näiteks on arvud: [1, 2, 3, 5, 6, 8]

Ühendamise tulemus:

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

See on kasulik andmete salvestamise või kuvamise optimeerimiseks, kui järjestikuseid numbreid saab kompaktsemalt esitada vahemikuna.

Lahenduse peamised sammud:

1. Sorteerida arvude massiiv.
2. Itereerida sorteeritud nimekirja, moodustades praeguse vahemiku.
3. Kui järgmine element on naabri (praegune + 1), laiendada vahemikku.
4. Kui mitte, salvesta praegune vahemik ja alusta uut.

Algoritmi keerukus — O(n log n) sorteerimise tõttu, kus n on arvude arv.

Python näide:

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

# Näide
print(collapse_ranges([1,2,3,5,6,8]))  # [(1,3), (5,6), (8,8)]