Insert Interval

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

Tek geçişli çözüm, her aralık bir kez kopyalandığı veya birleştirildiği için O(n) zamanda çalışır ve en fazla n+1 aralık içeren bir sonuç için O(n) alan kullanır. Aralığı eklemek ve yeniden sıralamak 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ışabileceği sıralanmamış bir listeyle başlar; bu yüzden önce listeyi sıralar. Burada liste sıralıdır ve eski aralıklar birbirine hiç değmez; bu nedenle birleştirmeyi yalnızca yeni aralık tetikleyebilir ve birleştirdiği aralıklar tek bir kesintisiz grup oluşturur. Tek bir geçiş yeterlidir.

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

[a, b] ve [c, d] , tam olarak a ≤ d ve c ≤ b olduğunda bir noktayı paylaşır. Bu, bu problemde istendiği gibi [2, 4] ve [4, 8] gibi uç uca değen aralıkları da örtüşen aralıklar olarak sayar. Uç uca değen aralıkları ayrı tutmak için a < d ve c < b kullanın.

OrtaAralıklar

+10

Başlangıç değerine göre sıralanmış aralıklar iki dizi olarak verilir: i aralığı [starts[i], ends[i]] şeklindedir ve hiçbir ikisi üst üste gelmez veya birbirine değmez. Yeni [newStart, newEnd] aralığını ekleyin, üst üste geldiği veya değdiği her aralıkla birleştirin ve tüm aralıkları başlangıç değerine göre sıralanmış [start, end] çiftleri olarak döndürün.

Aralıklar, biri diğerinin başladığı yerde sona erdiğinde birbirine değer; örneğin [2, 4] ve [4, 8] gibi. Birbirine değen aralıklar birleştirilir. [1, 2] ve [3, 4] hiçbir noktayı paylaşmadığından ayrı kalır.

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ırayla
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: eklemeden sonraki aralıkları, başlangıca göre sıralanmış [start, end] çiftleri olarak

Kısıtlar

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: aralıklar başlangıç zamanlarına göre sıralıdır ve hiçbiri birbiriyle ç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 örtüşür; bu nedenle üçü [5, 12] olur. [1, 3], 6'dan önce biter ve [15, 18], 12'den sonra başlar; bu nedenle 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] ile ve 8 noktasında [8, 9] ile birleşir; böylece üçü de [2, 9] aralığında birleşir.

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 komşularının hiçbirine değmez; bu yüzden aralarına yerleşir ve hiçbir şey birleşmez.

Ek soru

Birbiri ardına çok sayıda aralık eklersen, her ekleme O(log n) maliyetine ve yuttuğu her eski aralık için bir adıma mal olacak şekilde bunları nasıl saklarsın?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Eski aralıklar sıralı ve birbirinden ayrıdır; bu nedenle birleştirmeye yalnızca yeni aralık neden olabilir. Bu, listeyi üç parçaya ayırır: yeni aralık başlamadan önce biten aralıklar, onunla çakışan veya ona değen aralıklar ve yeni aralık bittikten sonra başlayan aralıklar. İlk parçayı kopyala, ortadaki parçayı tek bir aralıkta birleştir, son parçayı kopyala. Tek geçiş, sıralama yok.

Onu ekleyin ve her şeyi yeniden birleştirin

Sezgi

Aralıkları Birleştirme’yi yeniden kullan: yeni aralığı ekle, n+1 aralığın tümünü başlangıç değerine göre sırala ve son birleştirilen aralığı tutarak ilerle. Sıralamadan sonra bir aralık yalnızca hemen önündeki grupla çakışabilir; bu yüzden sıradaki başlangıç, tutulan bitiş değerinde veya daha önceyse bitişi genişlet; aksi takdirde bir boşluk oluşur ve yeni bir aralık başlar.

Sıralama, tek bir yerde sırası bozulmuş bir listeyi düzeltmek için O(n log n) maliyet getirir ve eski aralıkların hiçbir zaman birbiriyle birleşmediği gerçeğini göz ardı eder.

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.
Sırayla ilerlerken birleştirilmiş son aralığı tut.
Sonraki başlangıç, tutulan bitişten küçük veya ona eşitse, tutulan bitişi iki bitişten büyük olanla güncelle.
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

Liste sıralanmıştır ve aralıkları birbirinden ayrıdır; bu nedenle yeni aralıkla kesişen aralıklar kesintisiz tek bir dizi oluşturur. Bu diziden önceki her şey için ends[i] < newStart koşulu geçerlidir: aralık, yeni aralık başlamadan önce biter. Koşul katıdır; çünkü tam newStart noktasında biten bir aralık yeni aralığa dokunur ve birleştirilmelidir.

Dizi içindeki starts[i] ≤ mergedEnd koşulunu sağlayan bir aralık, oluşturduğun aralıkla örtüşür veya ona dokunur; bu nedenle aralığın başlangıcını daha küçük, bitişini daha büyük değer yaparak onu genişletir. mergedEnd değerinden sonra başlayan ilk aralık diziyi bitirir; çünkü sonraki tüm aralıklar daha sağda başlar. Dizi boşsa yeni aralık tek başına eklenir. İlk örnekte [1, 3] kopyalanır, [5, 7] ve [10, 12], [6, 11] aralığını [5, 12] olacak şekilde genişletir ve [15, 18] kopyalanır. Her aralığa bir kez bakılır: O(n) zaman ve sonuç dışında ek bellek kullanımı yoktur.

Algoritma

Kopyalanan aralıkları, ends[i] < newStart koşulu sağlanırken sonuca ekleyin.
mergedStart = newStart ve mergedEnd = newEnd değerlerini ayarlayın.
starts[i] ≤ mergedEnd koşulu sağlanırken mergedStart değerini daha küçük başlangıca, mergedEnd değerini daha büyük bitişe ayarlayın ve ilerleyin.
[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

Birbirine değen aralıklar için yanlış eşitsizlikler. İ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. İlk test katıdır, ikincisi değildir.
mergedEnd + 1 ile karşılaştırmak. Bu, ortak noktaları olmayan [1, 2] ve [3, 4] aralıklarını birleştirir.
Birleştirilmiş başlangıç olarak newStart değerini korumak. [6, 11], [5, 7] aralığının içinde başladığından sonuç 5'ten başlar.
Yeni aralığı yalnızca bir şeyle çakıştığında eklemek. Bir boşluğa veya iki uçtan birinin ötesine düştüğünde (örneğin [5, 6]), orta döngü hiç çalışmaz; ancak yine de eklenmesi gerekir.
i < n kontrolünü yapmadan önce starts[i] değerini okumak. Son aralığın ötesine uzanan yeni bir aralık, dizin sınırının dışına çıkar.

Sıkça sorulan sorular3

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

Tek geçişli çözüm, her aralık bir kez kopyalandığı veya birleştirildiği için O(n) zamanda çalışır ve en fazla n+1 aralık içeren bir sonuç için O(n) alan kullanır. Aralığı eklemek ve yeniden sıralamak 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ışabileceği sıralanmamış bir listeyle başlar; bu yüzden önce listeyi sıralar. Burada liste sıralıdır ve eski aralıklar birbirine hiç değmez; bu nedenle birleştirmeyi yalnızca yeni aralık tetikleyebilir ve birleştirdiği aralıklar tek bir kesintisiz grup oluşturur. Tek bir geçiş yeterlidir.

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

[a, b] ve [c, d], tam olarak a ≤ d ve c ≤ b olduğunda bir noktayı paylaşır. Bu, bu problemde istendiği gibi [2, 4] ve [4, 8] gibi uç uca değen aralıkları da örtüşen aralıklar olarak sayar. Uç uca değen aralıkları ayrı tutmak için a < d ve c < b kullanın.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

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