აღწერეთ მეზობელი რიცხვების დაჯგუფების დავალება.

კოალიციის მისია მეზობელი რიცხვების გაერთიანებაა, რაც გულისხმობს მინიმალური რაოდენობის უწყვეტი ინტერვალების (დიაპაზონების) შექმნას, რომლებიც ამ რიცხვებს მთლიანად იფარავენ.

მაგალითად, რიცხვები: [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)]