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