Insert Interval

Q: Berapa kompleksitas waktu untuk Insert Interval?

Solusi satu lintasan berjalan dalam waktu O(n) , karena setiap interval disalin atau digabungkan satu kali, dan menggunakan ruang O(n) untuk hasil yang berisi hingga n+1 interval. Menambahkan interval lalu mengurutkan ulang membutuhkan waktu O(n log n) .

Q: Apa perbedaan Insert Interval dengan Merge Intervals?

Merge Intervals dimulai dari list yang belum diurutkan, tempat interval mana pun dapat tumpang tindih dengan interval lainnya, jadi list tersebut diurutkan terlebih dahulu. Di sini, list sudah diurutkan dan interval lama tidak pernah bersentuhan, jadi hanya interval baru yang dapat memicu penggabungan, dan interval yang digabung dengannya membentuk satu rangkaian. Satu kali lintasan sudah cukup.

Q: Bagaimana cara memeriksa apakah dua interval saling tumpang tindih?

[a, b] dan [c, d] berbagi satu titik tepat ketika a ≤ d dan c ≤ b . Dengan begitu, interval yang bersentuhan seperti [2, 4] dan [4, 8] dihitung sebagai tumpang tindih, sesuai keinginan soal ini. Agar interval yang bersentuhan tetap terpisah, gunakan a < d dan c < b .

SedangInterval

+10

Kamu mendapatkan interval yang diurutkan berdasarkan titik awal dalam dua array: interval i adalah [starts[i], ends[i]], dan tidak ada dua interval yang tumpang tindih atau bersentuhan. Sisipkan interval baru [newStart, newEnd], gabungkan dengan setiap interval yang tumpang tindih atau bersentuhan dengannya, lalu kembalikan semua interval sebagai pasangan [start, end] yang diurutkan berdasarkan titik awal.

Interval bersentuhan ketika titik akhir salah satunya berada di titik awal yang lain, seperti pada [2, 4] dan [4, 8], dan interval yang bersentuhan akan digabungkan. [1, 2] dan [3, 4] tidak memiliki titik yang sama, jadi keduanya tetap terpisah.

Fungsi

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

startsinteger-array: awal setiap interval, dalam urutan menaik
endsinteger-array: akhir setiap interval, mencocokkan titik awal
newStartinteger: awal interval yang akan disisipkan
newEndinteger: ujung interval yang akan disisipkan
Mengembalikaninteger-2d-array: interval setelah penyisipan sebagai pasangan [start, end], diurutkan berdasarkan start

Batasan

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: interval diurutkan berdasarkan waktu mulai, dan tidak ada dua interval yang tumpang tindih atau bersentuhan.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Contoh

Input: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Output: [[1, 3], [5, 12], [15, 18]]
Penjelasan: [6, 11] bertumpang tindih dengan [5, 7] dan [10, 12], sehingga ketiganya menjadi [5, 12]. [1, 3] berakhir sebelum 6 dan [15, 18] dimulai setelah 12, sehingga keduanya tetap.

Input: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Output: [[2, 9]]
Penjelasan: [4, 8] bersentuhan dengan [2, 4] pada 4 dan [8, 9] pada 8, sehingga ketiganya bergabung menjadi [2, 9].

Input: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Output: [[1, 2], [5, 6], [9, 10]]
Penjelasan: [5, 6] berada di celah antara 2 dan 9 dan tidak menyentuh keduanya, jadi bagian itu ditempatkan di antara keduanya dan tidak ada yang digabungkan.

Pertanyaan lanjutan

Jika kamu menyisipkan banyak interval satu demi satu, bagaimana kamu akan menyimpannya agar setiap penyisipan membutuhkan biaya O(log n) ditambah satu langkah untuk setiap interval lama yang ditelannya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Interval lama sudah terurut dan saling terpisah, jadi hanya interval baru yang dapat menyebabkan penggabungan. Ini membagi list menjadi tiga bagian: interval yang berakhir sebelum interval baru dimulai, interval yang tumpang tindih atau bersentuhan dengannya, dan interval yang dimulai setelah interval baru berakhir. Salin bagian pertama, gabungkan bagian tengah menjadi satu interval, lalu salin bagian terakhir. Satu kali lintasan, tanpa pengurutan.

Tambahkan itu dan gabungkan semuanya lagi

Intuisi

Gunakan kembali Penggabungan Interval: tambahkan interval baru, urutkan semua n+1 interval berdasarkan titik awal, lalu telusuri sambil menyimpan interval terakhir yang digabungkan. Setelah pengurutan, sebuah interval hanya dapat tumpang tindih dengan kelompok tepat sebelumnya, jadi saat titik awal berikutnya berada di titik akhir yang disimpan atau sebelumnya, panjangkan titik akhirnya; jika tidak, akan terbentuk celah dan interval baru dimulai.

Pengurutan membutuhkan biaya O(n log n) untuk memperbaiki daftar yang hanya memiliki satu bagian yang tidak berurutan, dan cara ini mengabaikan bahwa interval lama tidak pernah bergabung satu sama lain.

Algoritma

Pasangkan setiap awal dengan akhirnya, lalu tambahkan [newStart, newEnd] ke dalam list.
Urutkan interval berdasarkan awalnya.
Telusuri interval secara berurutan sambil menyimpan interval terakhir yang digabungkan.
Jika awal berikutnya kurang dari atau sama dengan akhir yang disimpan, ubah akhir yang disimpan menjadi nilai yang lebih besar di antara kedua akhir.
Jika tidak, tambahkan interval berikutnya sebagai interval gabungan baru. Kembalikan list gabungan tersebut.

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

Satu lintasan dalam tiga bagian

Intuisi

list sudah diurutkan dan interval-intervalnya terpisah, jadi interval yang bertemu dengan interval baru membentuk satu rangkaian yang tidak terputus. Semua yang berada sebelum rangkaian memiliki ends[i] < newStart: interval itu berakhir sebelum interval baru dimulai. Pengujiannya menggunakan perbandingan ketat karena interval yang berakhir tepat pada newStart bersentuhan dengan interval baru dan harus digabungkan.

Di dalam rangkaian, interval dengan starts[i] ≤ mergedEnd tumpang tindih atau bersentuhan dengan interval yang sedang kamu buat, sehingga interval itu memperluasnya dengan mengambil awal yang lebih kecil dan akhir yang lebih besar. Interval pertama yang dimulai setelah mergedEnd mengakhiri rangkaian, karena setiap interval berikutnya dimulai lebih ke kanan. Jika rangkaiannya kosong, interval baru dimasukkan sendiri. Pada contoh pertama, [1, 3] disalin, [5, 7] dan [10, 12] memperluas [6, 11] menjadi [5, 12], dan [15, 18] disalin. Setiap interval diperiksa satu kali: waktu O(n), dan tidak menggunakan memori selain untuk hasil.

Algoritma

Salin interval ke hasil selama ends[i] < newStart.
Tetapkan mergedStart = newStart dan mergedEnd = newEnd.
Selama starts[i] ≤ mergedEnd, tetapkan mergedStart ke nilai awal yang lebih kecil dan mergedEnd ke nilai akhir yang lebih besar, lalu lanjutkan.
Tambahkan [mergedStart, mergedEnd].
Salin interval yang tersisa dan kembalikan hasilnya.

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

Jebakan dan kasus tepi

Ketidaksamaan yang salah untuk interval yang bersentuhan. Dengan ends[i] ≤ newStart di perulangan pertama, atau starts[i] < mergedEnd di perulangan kedua, [2, 4] dan [4, 8] tetap terpisah. Pengujian pertama bersifat ketat, sedangkan yang kedua tidak.
Membandingkan dengan mergedEnd + 1. Ini menggabungkan [1, 2] dan [3, 4], padahal keduanya tidak memiliki titik yang sama.
Mempertahankan newStart sebagai awal interval gabungan. [6, 11] dimulai di dalam [5, 7], jadi hasilnya dimulai dari 5.
Menambahkan interval baru hanya ketika interval itu tumpang tindih dengan interval lain. Saat interval itu berada di celah atau melewati salah satu ujung, seperti [5, 6], perulangan tengah tidak berjalan, tetapi interval itu tetap harus ditambahkan.
Membaca starts[i] sebelum memeriksa i < n. Interval baru yang mencapai melewati interval terakhir akan membuat indeks melewati batas.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk Insert Interval?

Solusi satu lintasan berjalan dalam waktu O(n), karena setiap interval disalin atau digabungkan satu kali, dan menggunakan ruang O(n) untuk hasil yang berisi hingga n+1 interval. Menambahkan interval lalu mengurutkan ulang membutuhkan waktu O(n log n).

Apa perbedaan Insert Interval dengan Merge Intervals?

Merge Intervals dimulai dari list yang belum diurutkan, tempat interval mana pun dapat tumpang tindih dengan interval lainnya, jadi list tersebut diurutkan terlebih dahulu. Di sini, list sudah diurutkan dan interval lama tidak pernah bersentuhan, jadi hanya interval baru yang dapat memicu penggabungan, dan interval yang digabung dengannya membentuk satu rangkaian. Satu kali lintasan sudah cukup.

Bagaimana cara memeriksa apakah dua interval saling tumpang tindih?

[a, b] dan [c, d] berbagi satu titik tepat ketika a ≤ d dan c ≤ b. Dengan begitu, interval yang bersentuhan seperti [2, 4] dan [4, 8] dihitung sebagai tumpang tindih, sesuai keinginan soal ini. Agar interval yang bersentuhan tetap terpisah, gunakan a < d dan c < b.

def insertInterval(starts, ends, newStart, newEnd):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

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