Merge Intervals
Sana, her biri başlangıçtan bitişe kadar tam sayılardan oluşan bir aralık olan bir aralık kümesi verilir. Örtüşen her aralık grubunu tüm grubu kapsayan tek bir aralıkta birleştir ve birleştirilmiş aralıkları başlangıçlarına göre sıralı olarak döndür. Yalnızca uç noktaları çakışan [1, 4] ve [4, 5] gibi aralıklar da örtüşüyor sayılır.
Aralıklar aynı uzunluktaki iki dizi olarak verilir: i aralığı [starts[i], ends[i]] şeklindedir. [start, end] çiftlerinden oluşan bir liste olan 2 boyutlu bir dizi döndürürsün.
Fonksiyon
- startsinteger-array
- her aralığın başlangıcı
- endsinteger-array
- her aralığın sonunda, başlangıcıyla aynı indekste
- Döndürürinteger-2d-array
- birleştirilmiş aralıklar, başlangıca göre sıralanmış [start, end] çiftleri olarak
Kısıtlar
1 ≤ starts.length == ends.length ≤ 1040 ≤ starts[i] ≤ ends[i] ≤ 104- Aralıklar herhangi bir sırayla gelir.
- Yalnızca uç noktalarında temas eden aralıklar çakışıyor sayılır.
Örnekler
- Girdi
- starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
- Çıktı
- [[1, 7], [12, 14]]
- Açıklama
- Başlangıç sırasına göre [1, 4], [3, 6] ile çakışır; [3, 6] da [5, 7] ile çakışır, bu yüzden üçü [1, 7] olur. [12, 14], 7'den sonra başlar ve tek başına kalır.
- Girdi
- starts = [6, 1]ends = [9, 6]
- Çıktı
- [[1, 9]]
- Açıklama
- Aralıklar [6, 9] ve [1, 6]. 6 noktasını paylaşırlar ve temas etmek örtüşme sayıldığından [1, 9] olarak birleşirler.
Ek soru
Aralıklar zaten birleştirilmiş ve başlangıç değerlerine göre sıralanmış olarak geliyor; senin de yeni bir aralık eklemen gerekiyor. Yeniden sıralama yapmadan, birleştirilmiş listeyi O(n) sürede döndürebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
İki ayrı dizi yerine tam aralıklarla çalışabilmek için önce her başlangıcı bitişiyle eşleştir.
Aralıkları başlangıç değerine göre sırala. Bundan sonra bir aralık yalnızca hemen önündeki grupla çakışabilir, daha gerideki bir grupla asla çakışamaz.
Son birleştirilmiş aralığı elde tutarak sıralı aralıklar üzerinde ilerleyin. Sonraki başlangıç değeri, bu aralığın bitiş değerinden küçük veya ona eşitse, bitiş değerini iki bitiş değerinden büyük olanla değiştirin. Aksi takdirde bu grup tamamlanmıştır ve sonraki aralık yeni bir grup başlatır.
Çözüm
Herhangi bir sırada çiftleri birleştirmek tekrarlanan geçişler gerektirir; çünkü her birleştirme bir aralığı genişletir ve daha önce kontrol ettiğiniz aralıklara ulaşmasını sağlar. Bunun yerine başlangıç değerine göre sıralayın. Böylece bir aralık yalnızca oluşturduğunuz grupla örtüşebilir ve tek geçişte iş tamamlanır.
Örtüşen çiftleri hiçbir şey değişmeyene kadar birleştir
Doğru, ama en büyük testlerde bitmiyor
Sezgi
[a, b] ve [c, d] aralıkları, c ≤ b ve a ≤ d olduğunda çakışır; [min(a, c), max(b, d)] ise her ikisini de kapsar. Her birleştirme bir aralığı ortadan kaldırır, bu yüzden süreç sona erer ve tam bir geçişte hiçbir çakışma bulunmadığında geriye kalan hiçbir iki aralık ortak bir noktayı paylaşmaz. Tek bir geçiş yeterli değildir: birleştirilmiş aralık daha geniştir ve geçişin daha önceki bir noktasında küçük parçasıyla karşılaştırılmış olduğu bir aralığa artık ulaşabilir.
Bir geçiş yaklaşık n²/2 çift karşılaştırır ve n geçişe kadar gerekebilir: O(n³). 10^4 aralık üzerinde tek bir geçiş bile 5 × 10^7 karşılaştırma demektir.
Algoritma
startsveendsdeğerlerini kopyalayın ve canlı aralıkların sayısınınile tutun.- Her
iaralığını kendisinden sonraki herjaralığıyla karşılaştırın. Çakışıyorlarsaiaralığınıjaralığını kapsayacak şekilde genişletin, son canlı aralığıjyuvasına taşıyın vendeğerini bir azaltın. - Birleştirmeden sonra
jyuvasını yeniden kontrol edin; çünkü artık orada farklı bir aralık bulunuyor. - Birleştirme yapılmayan bir geçiş gerçekleşene kadar geçişleri tekrarlayın.
- Her canlı başlangıcı bitişiyle eşleştirin, çiftleri başlangıca göre sıralayın ve döndürün.
def mergeIntervals(starts, ends):
s = list(starts)
e = list(ends)
n = len(s)
changed = True
while changed:
changed = False
i = 0
while i < n:
j = i + 1
while j < n:
if s[j] <= e[i] and s[i] <= e[j]:
# Intervals i and j overlap: interval i absorbs interval j.
s[i] = min(s[i], s[j])
e[i] = max(e[i], e[j])
# Move the last interval into slot j and drop the last slot.
n -= 1
s[j] = s[n]
e[j] = e[n]
changed = True
else:
j += 1
i += 1
return sorted([s[k], e[k]] for k in range(n))Başlangıç değerine göre sırala ve bir kez tarama yap
Sezgi
Başlangıca göre sıraladıktan sonra, sonraki aralık son gruptaki herhangi bir şeyden daha önce başlamaz; bu grup e noktasında biter. Başlangıcı en fazla e ise grupla örtüşür ya da ona dokunur ve gruba katılır; e, iki bitiş değerinden büyük olanı olur. Başlangıcı e noktasını geçiyorsa, daha sonraki hiçbir aralık da gruba geriye dönerek ulaşamaz; çünkü daha sonraki aralıklar daha sağda başlar. Grup tamamlanır ve bu aralık yeni bir grup başlatır.
Sıralama O(n log n) maliyetindedir ve tarama her aralığı bir kez ziyaret eder. Gruplar soldan sağa kapanır; bu nedenle sonuç başlangıca göre sıralı çıkar.
Algoritma
- Her başlangıcı kendi bitişiyle eşleştir:
iaralığı[starts[i], ends[i]]şeklindedir. - Çiftleri başlangıç değerine göre sırala.
- Sıralanmış çiftlerin üzerinden geç. Sonuç boşsa veya çift, son birleştirilmiş aralığın bitişinden sonra başlıyorsa çifti yeni bir aralık olarak ekle.
- Aksi takdirde son birleştirilmiş aralığın bitişini, kendi bitişi ile çiftin bitişinden büyük olan değer olarak ayarla.
- Birleştirilmiş listeyi döndür.
def mergeIntervals(starts, ends):
intervals = sorted(zip(starts, ends))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
if end > merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
Tuzaklar ve uç durumlar
≤yerine<ile karşılaştırmak.[1, 4]ve[4, 5]gibi uç uca değen aralıklar birleştirilmelidir.- Bitiş değerini iki aralıktan büyük olanı yerine yeni aralığın bitişi olarak ayarlamak.
[1, 10]aralığının ardından gelen[2, 3],[1, 10]olarak kalmalıdır. startsdizisini tek başına sıralayıp ardındanendsdizisini yeni konumlarından okumak; böylece bir başlangıç değeri başka bir aralığın bitiş değerini alır. Önce ikilileri eşleştirin veya indeksleri sıralayın.- Son birleştirilmiş aralık yerine önceki girdi aralığıyla karşılaştırmak.
[1, 10],[2, 3],[4, 5]dizisinde üçüncü aralık,[2, 3]aralığına değmese de[1, 10]aralığının içinde yer alır. - C'de
*returnSizedeğerini birleştirilmiş aralıkların sayısına ve her sütunun boyutunu 2'ye ayarlamamak.
Sıkça sorulan sorular3
Birleştirme Aralıkları'nın zaman karmaşıklığı nedir?
Sıralama ve tarama çözümü, n aralık için O(n log n) zamanda çalışır: sıralama O(n log n), tarama ise O(n) maliyetlidir. Sıralanmış çiftler ve sonuç için O(n) ek alan kullanır.
Aralıkları bitişe göre değil de başlangıca göre neden sıralıyoruz?
Başlangıca göre sıralandığında bir aralık yalnızca oluşturmakta olduğun grupla örtüşebilir; bu nedenle bu grubun bitişiyle yapılacak tek bir karşılaştırma her şeyi belirler. Bitişe göre sıralandığında, daha sonraki bir aralık daha önce kapattığın gruplardan önce başlayabilir: [5, 6], [1, 10]'dan önce gelir ve ileri doğru tarama başlangıç olarak yanlışlıkla 5'i korur.
Aralıkları ek alan kullanmadan birleştirebilir misin?
Evet, girdiyi değiştirebiliyorsan. Aralıkları yerinde sırala, ardından birleştirilen her aralığı aynı dizinin başına yaz ve yazılan son aralığın indeksini tut. Zaman karmaşıklığı O(n log n) olarak kalır ve kullanılan tek ek alan, dilinin sıralama işleminin kullandığı alandır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def mergeIntervals(starts, ends):
# Kodu buraya yazınTest #1
Test #2
Argümanlar
starts = [5, 1, 12, 3] ends = [7, 4, 14, 6]
Beklenen Çıktı
[[1, 7], [12, 14]]