Aprašykite užduotį suartėjusių skaičių sujungimui į intervalus.

Užduotis sujungti šalia esančius skaičius į intervalus yra sukurti minimalų nuoseklių intervalų (diapazonų) skaičių, kurie apima visus šiuos skaičius be spragų.

Pavyzdžiui, yra skaičių: [1, 2, 3, 5, 6, 8]

Sujungimo rezultatas:

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

Tai naudinga optimizuojant duomenų saugojimą ar rodymą, kai nuoseklūs skaičiai gali būti glaustai pateikti kaip diapazonas.

Pagrindiniai sprendimo žingsniai:

1. Surūšiuoti skaičių masyvą.
2. Iteruoti per surūšiuotą sąrašą, formuojant esamą diapazoną.
3. Jei sekantis elementas yra šalia (esamas + 1), išplėsti diapazoną.
4. Jei ne, išsaugoti esamą diapazoną ir pradėti naują.

Algoritmo sudėtingumas — O(n log n) dėl rūšiavimo, kur n yra skaičių kiekis.

Python pavyzdys:

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

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