Նկարագրեք հարևան թվերի խմբավորումը տիրույթներում։

Անցնող թվերը միավորելու խնդիրն այն է, որ ձևավորել նվազագույն շարունակական միջակայքներ (տարածքներ), որոնք ընդգրկում են բոլոր այդ թվերը առանց բացթողումների:

Օրինակ, կան թվեր՝ [1, 2, 3, 5, 6, 8]

Միավորման արդյունքը՝

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

Այս մոտեցումը օգտակար է տվյալների պահպանումը կամ ցուցադրությունը օպտիմալացնելու համար, երբ հաջորդական թվերը կարելի է կոմպակտ կերպով ներկայացնել որպես տարածք:

Հիմնական քայլերը՝

1. Սորտավորել թվերի զանգվածը:
2. Իտերացեք սորտավորված ցուցակի վրա՝ ձևավորելով ընթացիկ տարածքը:
3. Եթե հաջորդ տարրը հարևան է (հետին + 1), ընդլայնեք տարածքը:
4. Եթե ոչ, պահեք ընթացիկ տարածքը և սկսեք նոր:

Ալգորիթմի բարդությունը՝ O(n log n), սորտավորման պատճառով, որտեղ n թվերի քանակն է:

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

# Օրինակ
print(collapse_ranges([1,2,3,5,6,8]))  # [(1,3), (5,6), (8,8)]