Insert Interval

Q: Insert Interval'ın zaman karmaşıklığı nedir?

Tek geçişli çözüm O(n) zamanda çalışır: her aralık tam olarak bir kez kopyalanır veya birleştirilir. Sonuç en fazla n+1 aralık içerir; dolayısıyla O(n) alan kullanır ve girdiyle birlikte büyüyen başka hiçbir şey yoktur. Aralığı ekleyip yeniden sıralamak bunun yerine O(n log n) zaman alır.

Q: Insert Interval, Merge Intervals'tan nasıl farklıdır?

Merge Intervals, herhangi bir aralığın başka herhangi bir aralıkla çakışabildiği sıralanmamış bir listeyle başlar; bu yüzden önce sıralama yapması gerekir. Insert Interval'da liste zaten sıralıdır ve eski aralıklar birbirine hiç değmez; bu nedenle birleştirmeyi yalnızca yeni aralık tetikleyebilir. Birleştirdiği aralıklar kesintisiz tek bir dizi oluşturur; bu yüzden sıralama yapmadan tek bir geçiş yeterlidir.

Q: İki aralığın çakışıp çakışmadığını nasıl kontrol edersin?

[a, b] ve [c, d] aralıkları, tam olarak a ≤ d ve c ≤ b olduğunda en az bir noktayı paylaşır. Buna, bu problemin istediği gibi, [2, 4] ve [4, 8] gibi uç uca değen aralıkların örtüşmesi de dahildir. Uç uca değen aralıkların ayrı kalması gerekseydi, bunun yerine a < d ve c < b kullanırdınız.

Q: İkili arama, Insert Interval işlemini daha hızlı hâle getirebilir mi?

İkili arama, başlangıçlar ve bitişler sıralı olduğundan birleştirilmiş aralığın nerede başlayıp bittiğini O(log n) içinde bulur. Ancak işlev yine de yeni bir liste döndürür ve değişmeden kalan aralıkları bu listeye kopyalamak O(n) maliyet getirir. Dolayısıyla toplam süre O(n) olarak kalır. Aralıklar, dengeli bir ağaç gibi bir aralığı kopyalama yapmadan kaldırıp ekleyebilen bir yapıda bulunduğunda ikili arama avantaj sağlar.

OrtaAralıklar

+10

Başlangıç değerlerine göre sıralanmış bir aralık listesi alıyorsun; bu liste, aynı uzunlukta iki dizi olarak veriliyor: i. aralık [starts[i], ends[i]] şeklindedir. Bu aralıklardan hiçbiri örtüşmez veya birbirine değmez. Ayrıca yeni bir aralık, [newStart, newEnd], alıyorsun. Bu aralığı ekle, örtüştüğü veya değdiği her aralıkla birleştir ve başlangıç değerlerine göre sıralanmış, [start, end] çiftlerinden oluşan 2 boyutlu bir dizi olarak tüm aralıkları döndür.

Bir aralığın bitiş noktası diğerinin başlangıç noktasıysa bu iki aralık birbirine değer; örneğin [2, 4] ve [4, 8] gibi. Birbirine değen aralıklar tek bir aralıkta birleştirilir. [1, 2] ve [3, 4] hiçbir noktayı paylaşmaz, bu yüzden ayrı kalırlar.

Fonksiyon

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: her aralığın başlangıcı, artan sırada
endsinteger-array: her aralığın sonu, başlangıçlarla eşleşir
newStartinteger: eklenecek aralığın başlangıcı
newEndinteger: eklenecek aralığın sonu
Döndürürinteger-2d-array: ekleme işleminden sonraki aralıkları [start, end] çiftleri olarak, start değerine göre sıralanmış biçimde

Kısıtlar

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: aralıklar başlangıç zamanına göre sıralıdır ve hiçbir ikisi çakışmaz veya birbirine değmez.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Örnekler

Girdi: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Çıktı: [[1, 3], [5, 12], [15, 18]]
Açıklama: [6, 11], [5, 7] ve [10, 12] ile çakışır; bu yüzden üçü [5, 12] olur. [1, 3], 6'dan önce biter ve [15, 18], 12'den sonra başlar; bu yüzden ikisi de olduğu gibi kalır.

Girdi: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Çıktı: [[2, 9]]
Açıklama: [4, 8], 4 noktasında [2, 4] aralığına ve 8 noktasında [8, 9] aralığına değiyor. Değme, örtüşme sayıldığından üçünün birleşimi [2, 9] olur.

Girdi: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Çıktı: [[1, 2], [5, 6], [9, 10]]
Açıklama: [5, 6], 2 ile 9 arasındaki boşlukta yer alır ve iki komşusuna da değmez; bu yüzden aralarına yerleşir ve hiçbir şey birleşmez.

Gönderirken +20 gizli test

Ek soru

Aynı listeye art arda birçok yeni aralık eklediğinizi varsayalım. Her ekleme O(log n) maliyetine ve içine aldığı her eski aralık için bir adıma mal olacak şekilde aralıkları nasıl saklardınız?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Eski aralıklar zaten ayrı ve sıralı olduğundan, birleştirmeye yalnızca yeni aralık neden olabilir. Bu, listeyi üç gruba ayırır: yeni aralık başlamadan önce biten aralıklar, onunla örtüşen veya ona değen aralıklar ve o bitmeden sonra başlayan aralıklar. İlk grubu kopyalayın, ortadaki grubu tek bir aralıkta birleştirin, son grubu kopyalayın. Tek geçiş, sıralama yok.

Onu ekleyin ve her şeyi yeniden birleştirin

Sezgi

Merge Intervals problemini çözdüysen, burada da yeniden kullanabilirsin. Yeni aralığı listeye ekle, n+1 aralığın tümünü başlangıçlarına göre sırala ve birleştir. Sıralamadan sonra bir aralık yalnızca hemen önündeki grupla çakışabilir; bu yüzden son birleştirilmiş aralığı elinde tutarak listede ilerlersin. Sonraki başlangıç, bu aralığın bitişinde veya daha önceyse bitişi genişlet. Aksi hâlde arada gerçek bir boşluk vardır ve yeni bir aralık başlar.

İlk örnekte uygula. Liste [1, 3], [5, 7], [6, 11], [10, 12], [15, 18] hâline gelir. 5, 3'ten büyük olduğu için [1, 3] tek başına kalır. 6, 7'den küçük veya 7'ye eşit olduğu için [5, 7], [5, 11] aralığına genişler. 10, 11'den küçük veya 11'e eşit olduğu için [5, 12] aralığına genişler. 15, 12'den büyük olduğu için [15, 18] yeni bir aralık olarak başlar.

Bu doğru bir yöntemdir ve 2000 aralıkta hızlı çalışır. Ancak sana verilen iki bilgiyi göz ardı eder: liste zaten sıralıdır ve eski aralıklar hiçbir zaman birbiriyle birleşmez. Tek bir yerde sırası bozuk olan bir listeyi yeniden sıralamak için O(n log n) maliyetini üstlenmek, mülakat yapan kişinin senden kaldırmanı isteyeceği adımdır.

Algoritma

Her başlangıcı kendi bitişiyle eşleştir ve listeye [newStart, newEnd] ekle.
Aralıkları başlangıçlarına göre sırala.
Son birleştirilmiş aralığı tutarak aralıklar üzerinde sırayla ilerle.
Sonraki başlangıç, tutulan bitişten küçük veya ona eşitse tutulan bitişi iki bitişin büyük olanına yükselt.
Aksi hâlde sonraki aralığı yeni birleştirilmiş aralık olarak ekle. Birleştirilmiş listeyi döndür.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

Üç bölümde tek geçiş

Sezgi

Listeyi i indeksiyle bir kez dolaşın ve üç bölüme ayırın. İlk olarak, ends[i] < newStart koşulunu sağlayan her aralık yeni aralık başlamadan önce biter, dolayısıyla onunla hiçbir noktayı paylaşmaz: sonucu kopyalayın. Testte katı bir < kullanılır; çünkü tam olarak newStart noktasında biten bir aralık yeni aralığa değdiğinden birleştirilmelidir.

İkinci olarak, starts[i] ≤ mergedEnd koşulunu sağlayan her aralık oluşturduğunuz aralıkla örtüşür veya ona değer. Aralığı birleştirin: mergedStart daha küçük başlangıç, mergedEnd ise daha büyük bitiş olur. Liste sıralı olduğundan bu bölümdeki aralıklar yan yana gelir. Bir aralık mergedEnd değerinden sonra başladığında, sonraki tüm aralıklar daha da sağda başlar; dolayısıyla ondan sonraki hiçbir şey birleştirilemez. Birleştirilmiş aralığı ekleyin; bu adım, bölümün boş olduğu ve yeni aralığın tek başına eklendiği durumu da kapsar.

Üçüncü olarak, geriye kalan her şeyi kopyalayın. Bu aralıklar birleştirilmiş aralığın bitişinden sonra başlar ve zaten birbirlerinden ayrıdır.

İlk örneği adım adım izleyin. [1, 3], 6'dan önce biter: kopyalayın. [5, 7], en fazla 11 olan 5'te başlar: birleştirilmiş aralık [5, 11] olur. [10, 12], en fazla 11 olan 10'da başlar: aralık [5, 12] olur. [15, 18], 12'den sonra başlar; bu yüzden [5, 12] aralığını ekleyin ve [15, 18] aralığını kopyalayın. Her aralığa bir kez bakılır; dolayısıyla süre O(n) olur ve kullanılan tek ek bellek sonucun kendisidir.

Algoritma

ends[i] < newStart koşulu sağlanırken aralıkları sonuca kopyalayın.
mergedStart = newStart ve mergedEnd = newEnd olarak ayarlayın.
starts[i] ≤ mergedEnd koşulu sağlandığı sürece, mergedStart değerini daha küçük başlangıç, mergedEnd değerini daha büyük bitiş olacak şekilde ayarlayın ve devam edin.
[mergedStart, mergedEnd] değerini ekleyin.
Kalan aralıkları kopyalayın ve sonucu döndürün.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

Tuzaklar ve uç durumlar

Döngü kısa olduğundan hataların çoğu yanlış bir karşılaştırmadan veya listenin başındaki ya da sonundaki bir durumun unutulmasından kaynaklanır.

Değen aralıklar için yanlış eşitsizliği kullanmak. İlk döngüde ends[i] ≤ newStart veya ikinci döngüde starts[i] < mergedEnd kullanıldığında, [2, 4] ve [4, 8] ayrı kalır. Değen aralıklar birleştirilir; bu nedenle ilk test katı, ikincisi ise katı değildir.
Yalnızca bitişik gibi görünen aralıkları birleştirmek. [1, 2] ve [3, 4] ortak bir noktaya sahip değildir; bu nedenle mergedEnd + 1 ile karşılaştırma yapmak, ayrı kalması gereken aralıkları birleştirir.
Birleştirilmiş başlangıç olarak newStart değerini korumak. Yeni aralık eski bir aralığın içinde başladığında, [6, 11] değerinin [5, 7] içinde olması gibi, sonuç 5'ten başlar. İki başlangıç değerinden küçük olanı alın.
Yeni aralığı yalnızca bir aralıkla çakıştığında eklemek. Yeni aralık tüm aralıklardan önceye, tüm aralıklardan sonraya veya bir boşluğa düştüğünde orta döngü hiç çalışmaz; ancak yeni aralık yine de eklenmelidir.
i < n koşulunu kontrol etmeden önce starts[i] veya ends[i] değerini okumak. Yeni aralık son aralığın ötesine uzandığında indeks, dizilerin sonunu aşar.

Sıkça sorulan sorular4

Insert Interval'ın zaman karmaşıklığı nedir?

Tek geçişli çözüm O(n) zamanda çalışır: her aralık tam olarak bir kez kopyalanır veya birleştirilir. Sonuç en fazla n+1 aralık içerir; dolayısıyla O(n) alan kullanır ve girdiyle birlikte büyüyen başka hiçbir şey yoktur. Aralığı ekleyip yeniden sıralamak bunun yerine O(n log n) zaman alır.

Insert Interval, Merge Intervals'tan nasıl farklıdır?

Merge Intervals, herhangi bir aralığın başka herhangi bir aralıkla çakışabildiği sıralanmamış bir listeyle başlar; bu yüzden önce sıralama yapması gerekir. Insert Interval'da liste zaten sıralıdır ve eski aralıklar birbirine hiç değmez; bu nedenle birleştirmeyi yalnızca yeni aralık tetikleyebilir. Birleştirdiği aralıklar kesintisiz tek bir dizi oluşturur; bu yüzden sıralama yapmadan tek bir geçiş yeterlidir.

İki aralığın çakışıp çakışmadığını nasıl kontrol edersin?

[a, b] ve [c, d] aralıkları, tam olarak a ≤ d ve c ≤ b olduğunda en az bir noktayı paylaşır. Buna, bu problemin istediği gibi, [2, 4] ve [4, 8] gibi uç uca değen aralıkların örtüşmesi de dahildir. Uç uca değen aralıkların ayrı kalması gerekseydi, bunun yerine a < d ve c < b kullanırdınız.

İkili arama, Insert Interval işlemini daha hızlı hâle getirebilir mi?

İkili arama, başlangıçlar ve bitişler sıralı olduğundan birleştirilmiş aralığın nerede başlayıp bittiğini O(log n) içinde bulur. Ancak işlev yine de yeni bir liste döndürür ve değişmeden kalan aralıkları bu listeye kopyalamak O(n) maliyet getirir. Dolayısıyla toplam süre O(n) olarak kalır. Aralıklar, dengeli bir ağaç gibi bir aralığı kopyalama yapmadan kaldırıp ekleyebilen bir yapıda bulunduğunda ikili arama avantaj sağlar.

Python

def insertInterval(starts, ends, newStart, newEnd):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

Beklenen

[[1, 3], [5, 12], [15, 18]]