Temu Duga Pengekodan: Bagaimanakah Anda Menggabungkan Selang yang Bertindih?

Gesaan dan Skop

Diberikan senarai selang tertutup intervals yang tidak diisih, dengan setiap item ialah [start, end] dan start <= end, gabungkan semua pertindihan. Kembalikan senarai baharu yang diisih mengikut start, adalah tak bersilang secara berpasangan, dan meliputi titik yang sama persis. Masalah ini menggunakan selang tertutup, jadi [1, 4] dan [4, 5] berkongsi titik 4 dan mesti menjadi [1, 5]. Fungsi ini tidak boleh memutasi inputnya.

Sebagai contoh:

Input:  [[8, 10], [1, 3], [2, 6], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Input mungkin kosong dan boleh mengandungi selang pendua, titik akhir negatif, selang dengan panjang sifar, atau selang yang terkandung sepenuhnya di dalam selang lain. Masalah asas menjamin dua titik akhir integer yang sah bagi setiap item, jadi pengesahan format input berada di luar fungsi penggabungan. Ini adalah masalah pengekodan kejuruteraan perisian umum. Kemahiran terasnya adalah mengubah susunan sebarangan kepada susunan yang membolehkan keputusan setempat dibuat, kemudian membuktikan bahawa keputusan tamak tidak boleh terlepas sambungan terkemudian.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon mentakrifkan semantik selang. Selang tertutup, selang separuh terbuka, dan peraturan yang menggabungkan julat yang sekadar bersebelahan boleh menghasilkan syarat yang berbeza. Menulis start < current_end tanpa menyatakan kontrak boleh gagal dalam kes titik akhir yang dikongsi.

Isyarat kedua ialah sama ada calon boleh menerangkan mengapa pengisihan membantu. Selepas pengisihan, start seterusnya tidak boleh lebih kecil daripada start semasa. Jika ia sudah lebih besar daripada end bagi selang gabungan semasa, setiap start terkemudian juga akan lebih besar, jadi selang semasa selamat untuk dikeluarkan (di-emit). Jawapan yang kukuh memberikan hujah pemuktamadan ini dan bukan sekadar menyebut "isih dan imbas."

Isyarat ketiga ialah pengendalian pembendungan (containment). Apabila [1, 10] bertemu dengan [2, 3], end gabungan mestilah max(10, 3). Menulis ganti dengan 3 akan menghilangkan titik-titik yang diliputi. Pertindihan berantai juga mesti dibandingkan dengan selang gabungan yang sedang berkembang, bukan sekadar dengan selang input mentah sebelumnya.

Penemu duga juga akan memeriksa kontrak mutasi, kekompleksan, dan strategi pengesahan. Pengisihan lazimnya menentukan masa larian O(n log n). Pelaksanaan ini menggunakan ruang O(n) untuk salinan yang diisih dan hasil bagi memastikan input tidak berubah. Ujian sepatutnya melangkaui contoh standard: pastikan input tidak berubah, output teratur dan tak bersilang, dan hasil rawak sepadan dengan pelaksanaan rujukan yang perlahan.

Soalan Penjelasan Sebelum Menjawab

• Adakah ini selang tertutup atau separuh terbuka, dan adakah titik akhir yang dikongsi bergabung? Selang di sini adalah tertutup, jadi syaratnya ialah next_start <= current_end. Jika produk menganggap kedekatan bersebelahan secara berasingan, gunakan perbandingan ketat. Untuk [a, b), sama ada julat yang bersambungan tetapi tidak bertindih perlu digabungkan adalah pilihan yang berasingan.
• Adakah input telah diisih mengikut start? Input yang diisih hanya memerlukan imbasan linear, mengurangkan masa kepada O(n). Input yang tidak diisih memerlukan pengisihan atau kaedah khusus yang terikat pada domain titik akhir yang terhad.
• Bolehkah saya memutasi input? Jika ya, isih di tempat (in-place) dan padatkan dengan penunjuk tulis. Jika tidak, salin data atau gunakan operasi pengisihan yang mengembalikan senarai baharu.
• Adakah titik akhir integer daripada julat terhad yang kecil? Pengisihan perbandingan ialah pilihan langsung untuk nilai setanding sebarangan. Semesta integer kecil mungkin membenarkan baldi atau tatasusunan beza (difference array), tetapi kosnya bergantung pada julat koordinat dan bukan hanya pada n.
• Adakah ini satu penggabungan luar talian atau aliran berterusan? Aliran yang diisih mengikut start boleh digabungkan dan dikeluarkan secara dalam talian. Aliran dengan susunan sebarangan tidak boleh dimuktamadkan awal dengan selamat kerana selang pada masa hadapan mungkin bermula lebih awal dan merapatkan komponen yang sedia ada.
• Adakah output hanya memerlukan sempadan, atau adakah ia mesti mengekalkan metadata selang? Menggabungkan sempadan tidak mentakrifkan cara label, kebenaran, atau harga digabungkan. Metadata memerlukan peraturan pengagregatan yang eksplisit.

Rangka Kerja Jawapan 30 Saat

"Mula-mula saya akan mengesahkan bahawa ini ialah selang tertutup, titik akhir yang dikongsi dikira sebagai pertindihan, dan saya tidak boleh memutasi input. Saya akan menyalin dan mengisih mengikut start dan end, kemudian mengekalkan satu selang gabungan semasa. Jika start seterusnya berada pada atau sebelum end semasa, saya melanjutkan end kepada maksimum antara kedua-dua end tersebut. Jika tidak, tiada selang kemudian yang boleh mencapai selang semasa, jadi saya menambahkannya pada hasil dan memulakan julat baharu. Saya menambahkan julat terakhir selepas imbasan selesai. Pengisihan menelan kos O(n log n), imbasan menelan kos O(n), dan salinan yang diisih serta output menggunakan ruang O(n). Tak varian ketepatan ialah selang yang dikeluarkan adalah muktamad dan selang semasa ialah tepat komponen bersambung terakhir yang belum dikeluarkan."

Perincian Langkah demi Langkah

Pendekatan langsung berulang kali mencari mana-mana pasangan yang bertindih, menggantikannya dengan penyatuannya, dan memulakan semula sehingga tiada apa-apa yang berubah. Ia mudah dinyatakan dengan gelung bersarang, tetapi selang yang baru digabungkan mungkin bertindih dengan sesuatu yang telah diperiksa sebelum ini, jadi ia boleh memerlukan banyak laluan dan mencapai O(n²) atau lebih teruk. Kaedah tersebut berguna sebagai orakel ujian input kecil, tetapi merupakan penyelesaian utama yang lemah.

Pengisihan menukar masalah global kepada imbasan dari kiri ke kanan. Isih mengikut (start, end) secara menaik. Kekalkan current = [current_start, current_end], komponen gabungan akhir antara selang yang diproses yang belum dikeluarkan. Bagi setiap [start, end] seterusnya:

1. Jika start <= current_end, kedua-dua selang tertutup bertindih, jadi tetapkan current_end kepada max(current_end, end).
2. Jika start > current_end, terdapat jurang. Setiap start terkemudian adalah sekurang-kurangnya start, jadi tiada selang masa hadapan yang boleh mencapai current. Keluarkannya dan mulakan selang semasa yang baharu.

Imbasan mengekalkan tiga tak varian:

1. Selang yang dikeluarkan diisih, tak bersilang secara berpasangan, dan tidak akan berubah.
2. Penyatuan selang yang dikeluarkan dan current bersamaan dengan penyatuan semua selang input yang telah diproses.
3. current ialah komponen gabungan maksimum terakhir antara selang yang diproses dan satu-satunya komponen yang boleh bertindih dengan selang seterusnya.

Ketiga-tiga tak varian ini kekal sah selepas permulaan daripada selang pertama yang diisih. Pertindihan hanya melanjutkan titik akhir kanan komponen terakhir dan mengekalkan penyatuannya. Pada jurang, pengisihan menjamin bahawa setiap start masa hadapan terletak di luar current_end, jadi pengeluaran adalah selamat. Secara aruhan, tak varian kekal sepanjang imbasan. Mengeluarkan current sekali lagi pada penghujungnya menghasilkan penyatuan setara yang tiada pasangan boleh digabungkan lagi.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []

    ordered = sorted((start, end) for start, end in intervals)
    merged: list[list[int]] = []
    current_start, current_end = ordered[0]

    for start, end in ordered[1:]:
        if start <= current_end:
            current_end = max(current_end, end)
        else:
            merged.append([current_start, current_end])
            current_start, current_end = start, end

    merged.append([current_start, current_end])
    return merged

sorted() membina senarai terisih baharu, dan pembongkaran tupel tidak menulis semula senarai dalaman yang asal, jadi fungsi ini mematuhi kontrak tanpa mutasinya. Pengisihan perbandingan menelan kos O(n log n) dan imbasan menelan kos O(n), menjadikannya O(n log n) secara keseluruhan. Salinan yang diisih dan output yang mungkin mengandungi kesemua n selang adalah linear, jadi ruang termasuk output ialah O(n). Jika input sudah diisih, melangkau pengisihan memberikan masa O(n). Jika mutasi dibenarkan, pengisihan di tempat dan penunjuk tulis boleh menggunakan semula input, walaupun pelaksanaan pengisihan mungkin masih memerlukan ruang tindanan (stack) atau penimbal.

Pengesahan harus merangkumi input kosong, satu selang, semua selang tak bersilang, titik akhir yang dikongsi, pembendungan penuh, pendua, titik akhir negatif, dan pertindihan berantai. Contohnya, [[1, 2], [2, 3], [3, 4]] mesti menjadi [[1, 4]]; ini menangkap kod yang hanya membandingkan selang mentah yang bersebelahan. Simpan salinan mendalam (deep copy) dan pastikan panggilan fungsi tidak mengubahnya. Kemudian jana input rawak kecil dan bandingkan dengan orakel perlahan yang berulang kali menggabungkan mana-mana pasangan yang bertindih. Pelaksanaan di atas telah diuji secara kebezaan (differential-tested) pada 10,000 kes rawak dengan benih tetap.

Untuk nilai sebarangan dalam model perbandingan, isih dan imbas ialah jawapan umum yang jelas. Apabila n sangat kecil, penggabungan pasangan berulang mungkin lebih pendek dan batasannya yang lebih perlahan mungkin tidak menjadi masalah. Input yang sudah diisih hanya memerlukan imbasan. Domain integer terhad yang kecil mungkin mewajarkan baldi atau teknik tatasusunan beza yang kosnya bergantung pada semesta koordinat. Dalam temu duga, perkenalkan kes khas sedemikian hanya selepas kekangan mewajarkannya.

Contoh Jawapan Berkualiti Tinggi

"Mula-mula saya akan menjelaskan sempadannya: input mengandungi selang tertutup yang tidak diisih, berkongsi titik akhir dikira sebagai pertindihan, dan saya mesti mengembalikan data baharu. Ini bermakna [1, 4] dan [4, 5] menggunakan ujian kurang daripada atau sama dengan.

Versi brute-force boleh terus mencari pasangan dan memulakan semula, tetapi selang yang baru digabungkan mungkin bertindih dengan sesuatu yang dilihat lebih awal, jadi ia mungkin memerlukan banyak laluan. Saya akan mengisih mengikut start dan hanya mengekalkan satu selang yang belum dimuktamadkan. Apabila start seterusnya berada di dalam end-nya, saya melanjutkannya dengan end yang lebih besar. Jika tidak, saya menulisnya pada hasil dan memulakan komponen baharu.

Perbandingan penting adalah terhadap komponen yang terkumpul, bukan sekadar selang mentah sebelumnya. Pengisihan menjamin bahawa apabila start seterusnya melebihi end semasa, setiap start terkemudian juga melebihi, jadi hasil semasa adalah muktamad secara kekal. Oleh itu, awalan yang dikeluarkan kekal teratur dan tak bersilang, manakala selang semasa meliputi tepat komponen gabungan terakhir bagi input yang diproses.

Saya akan menggunakan sorted() untuk mengelak daripada mengubah senarai pemanggil dan mengembalikan nilai awal untuk input kosong. Masanya ialah O(n log n) untuk pengisihan ditambah imbasan linear, dan salinan terisih serta output menggunakan ruang O(n). Saya akan menguji selang yang bersentuhan, bersarang, pendua, negatif, dan berantai, kemudian melakukan ujian perbezaan terhadap penggabungan berpasangan yang perlahan sambil turut memastikan bahawa input tidak berubah."

Kesilapan Lazim

• Memilih < atau <= tanpa mentakrifkan semantik titik akhir → hasil titik akhir yang dikongsi bergantung pada kontrak → Nyatakan semantik tertutup lawan separuh terbuka dan sama ada julat yang bersambungan bergabung sebelum memilih syarat.
• Mengimbas dalam susunan asal → selang yang bertindih mungkin berada jauh dan selang masa hadapan boleh menyambung semula output yang telah dikeluarkan → Isih mengikut start, melainkan input yang diisih dijamin.
• Hanya membandingkan selang mentah bersebelahan → item ketiga dalam [1, 10], [2, 3], [9, 12] mesti bertemu dengan [1, 10] yang telah diperluas → Sentiasa bandingkan dengan hasil gabungan terakhir.
• Menetapkan current_end = end pada pertindihan → selang yang terkandung mengecilkan julat yang diliputi → Gunakan max(current_end, end).
• Terlupa penambahan terakhir (final append) → gelung yang hanya mengeluarkan pada jurang akan kehilangan komponen terakhir → Tambahkan current sekali selepas gelung.
• Membaca item pertama untuk input kosong → permulaan akan mencetuskan ralat indeks → Kembalikan senarai kosong sebelum pengisihan dan permulaan.
• Menjanjikan tiada mutasi tetapi mengisih di tempat → pemanggil melihat input yang disusun semula, dan senarai dalaman yang digunakan semula mungkin terus berubah → Gunakan sorted() dan objek hasil baharu, atau jadikan mutasi sebahagian daripada kontrak.
• Hanya menguji tatasusunan yang dijangkakan → pertindihan berantai, mutasi, dan ralat sempadan boleh kekal tersembunyi → Tambah pemeriksaan sifat dan orakel pembezaan rawak.
• Mendakwa O(n log n) sentiasa tidak dapat dielakkan → input yang diisih dan domain integer terhad yang kecil boleh mengelakkan pengisihan perbandingan → Hadkan tuntutan batas bawah kepada titik akhir setanding sebarangan yang tidak diisih.

Soalan Susulan dan Cara Mengendalikannya

Soalan Susulan 1: Apakah yang berubah jika titik akhir yang dikongsi tidak dikira sebagai pertindihan?

Ubah syarat daripada start <= current_end kepada start < current_end. Sahkan bahasa domain terlebih dahulu: selang tertutup yang berkongsi titik akhir sememangnya bersilang secara matematik, jadi produk yang memisahkannya sebenarnya meminta untuk menggabungkan hanya pertindihan dengan panjang positif. Untuk [a, b) separuh terbuka, [1, 4) dan [4, 5) tidak bertindih; penggabungan julat yang bersambungan kemudiannya merupakan satu lagi peraturan yang bebas.

Soalan Susulan 2: Input telah diisih dan mutasi dibenarkan. Bagaimanakah anda boleh mengurangkan ruang tambahan?

Langkau pengisihan dan padatkan ke dalam awalan input dengan penunjuk tulis. Penunjuk baca melawat selang baharu. Jika bertindih, kemas kini end pada kedudukan tulis; jika ada jurang, majukan penunjuk tulis dan salin selang baharu. Kembalikan panjang awalan atau paparan awalan tersebut. Imbasan mengambil masa O(n) dan ruang pembantu O(1) tanpa mengambil kira perwakilan yang dikembalikan, dengan kos memusnahkan input asal.

Soalan Susulan 3: Selang tiba secara berterusan dalam susunan start. Bolehkah anda mengeluarkan aliran?

Boleh. Kekalkan hanya current. Apabila start yang tiba melebihi end-nya, keluarkan current dan mulakan komponen seterusnya; keluarkan komponen terakhir apabila aliran ditutup. Memori kerja ialah O(1) tanpa mengambil kira output. Dengan susunan ketibaan sebarangan, selang masa hadapan boleh merapatkan dua komponen, jadi pengeluaran awal adalah tidak selamat. Gunakan penimbal, isih secara luaran, atau kekalkan struktur selang dinamik sebagai ganti.

Soalan Susulan 4: Bagaimana jika seratus juta selang tidak muat dalam memori?

Gunakan pengisihan luaran mengikut start: isih kelompok bersaiz memori kepada jarian (runs) yang teratur, kemudian lakukan k-way merge. Aliran cantuman sudah diisih mengikut start, jadi jalankan mesin keadaan satu selang yang sama semasa mencantumkan dan bukannya mematerialisasikan fail lengkap yang diisih secara global terlebih dahulu. Kerja perbandingan kekal mengikut tertib O(n log n); I/O cakera dan storan sementara menjadi kos tambahan yang penting.

Soalan Susulan 5: Bolehkah selang dengan harga atau label kebenaran digabungkan secara langsung?

Hanya sempadan geometrinya yang boleh disatukan oleh algoritma ini. Jika segmen yang bertindih mempunyai label yang berbeza, meruntuhkannya menjadi satu label akan menghilangkan maklumat. Tentukan sama ada output membawa satu set label, label keutamaan tertinggi, atau subsegmen minimum yang metadatanya adalah malar. Pilihan terakhir biasanya memerlukan sapuan (sweep) ke atas peristiwa titik akhir dan bukannya penyatuan selang yang mudah.