Leetcode 56 Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
  • Soruda bize bir interval listesi veriliyor.İntervalleri doğru parçaları olarak düşünebiliriz. Bu intervallerden kesişenleri birleştirip kesişmeyenleri de olduğu gibi bırakarak yeni bir liste oluşturup dönmemiz isteniyor.
  • Kesişen intervallerin birleşmesine örnek olarak [1,3] ve [2,6] listemizde varsa bunlar 2 ve 3 için kesişmektedir bu durumda döneceğimiz değer [1,6] olacaktır.
  • İlk yapacağımız işlem intervallerin başlangıç değerlerine göre listemizi küçükten büyüğe sıralamak olacaktır.
  • Daha sonra sıralanmış listedeki ilk intervali sonuç listemize ekleriz.
  • İlk interval eklendiği için 2. intervalden başlayarak bir for döngüsü kurarız.
  • Burada listedeki son elemanın bitiş değeri(lastEnd) ile intervaldeki elimizdeki elemanın başlangıç değerini(start) karşılaştırırız.
  • lastEnd değeri start değerinden büyük ise sonuç listemizdeki intervalin end değerini güncelleriz.
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # O(nLogn)
        
        intervals.sort(key = lambda i : i[0]) #intervalleri başlangıç değerlerine göre sırala
        output = [intervals[0]] #sıralanmış listedeki ilk intervali sonuç listesine ekle
        
        for start,end in intervals[1:]: #ilk interval eklendiği için 2. intervalden başla
            lastEnd = output[-1][1] #sonuç listemize eklediğimiz ilk intervalin bitiş değerini atarız
                
            if start <= lastEnd:
                output[-1][1] = max(lastEnd, end)
            else:
                output.append([start, end])
        return output