Merge Intervals: çakışan aralıkları birleştiren bir fonksiyon yazın. Örn. [[1,3],[2,6],[8,10]] -> [[1,6],[8,10]]

Aralıkları başlangıç noktasına göre sıralayıp tek geçişte birleştirmek yeterlidir. Sıralamadan sonra bir aralık yalnızca kendinden hemen önceki birleşik aralıkla çakışabilir.

Yaklaşım

1. Aralıkları start değerine göre sırala.
2. Sonuç listesinin son elemanına bak: yeni aralığın başlangıcı, sonun bitişinden küçük veya eşitse çakışma vardır; bitişi max ile güncelle.
3. Çakışma yoksa yeni aralığı listeye ekle.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))  # [[1, 6], [8, 10], [15, 18]]

Karmaşıklık

• Zaman: sıralama nedeniyle O(n log n), birleştirme geçişi O(n).
• Bellek: çıktı hariç sıralamanın kullandığı ek alan (Python'da Timsort O(n)'e kadar).

Dikkat edilecek noktalar

• [1,4] ve [4,5] dokunuyor mu? Soruyu sorana sorun; çoğu tanımda <= ile birleştirilir.
• max kullanmayı unutmak klasik hatadır: [1,10] ile [2,3] birleşince bitiş 10 kalmalıdır.