Wawancara Koding: Bagaimana Cara Menggabungkan Interval yang Tumpang Tindih?

Prompt dan Cakupan

Diberikan daftar interval tertutup intervals yang belum terurut, di mana setiap elemen adalah [start, end] dan start <= end, gabungkan semua interval yang saling tumpang tindih. Kembalikan daftar baru yang terurut berdasarkan start, saling lepas (pairwise-disjoint), dan mencakup titik-titik yang sama persis. Masalah ini menggunakan interval tertutup, sehingga [1, 4] dan [4, 5] berbagi titik 4 dan harus menjadi [1, 5]. Fungsi tersebut tidak boleh memutasi input aslinya.

Sebagai contoh:

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

Input mungkin kosong dan dapat berisi interval duplikat, titik akhir bernilai negatif, interval dengan panjang nol, atau interval yang sepenuhnya berada di dalam interval lain. Masalah dasar ini menjamin adanya dua titik akhir bilangan bulat yang valid per elemen, sehingga validasi format input berada di luar fungsi penggabungan. Ini adalah masalah koding rekayasa perangkat lunak umum. Keterampilan intinya adalah mengubah urutan arbitrer menjadi urutan yang memungkinkan pengambilan keputusan lokal, lalu membuktikan bahwa keputusan rakus (greedy) tersebut tidak akan melewatkan hubungan di kemudian hari.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah apakah kandidat mendefinisikan semantik interval. Interval tertutup, interval setengah terbuka, dan aturan yang menggabungkan rentang yang hanya berdampingan dapat menghasilkan kondisi yang berbeda. Menulis start < current_end tanpa menyatakan kontraknya dapat menggagalkan kasus titik akhir bersama.

Sinyal kedua adalah apakah kandidat dapat menjelaskan mengapa pengurutan membantu. Setelah pengurutan, start berikutnya tidak mungkin lebih kecil dari start saat ini. Jika start tersebut sudah lebih besar dari end interval gabungan saat ini, setiap start berikutnya juga akan lebih besar, sehingga interval saat ini aman untuk dikeluarkan (di-emit). Jawaban yang kuat memberikan argumen finalisasi ini alih-alih hanya mengatakan "urutkan dan pindai."

Sinyal ketiga adalah penanganan cakupan (containment). Saat [1, 10] bertemu [2, 3], end hasil penggabungan haruslah max(10, 3). Menimpanya dengan 3 akan menghilangkan titik-titik yang tercakup. Tumpang tindih berantai juga harus dibandingkan dengan interval gabungan yang sedang berkembang, bukan hanya dengan interval input mentah sebelumnya.

Pewawancara juga akan memeriksa kontrak mutasi, kompleksitas, dan strategi validasi. Pengurutan biasanya menentukan waktu eksekusi O(n log n). Implementasi ini menggunakan ruang O(n) untuk salinan terurut dan hasil guna menjaga input tidak berubah. Pengujian harus melampaui contoh standar: pastikan bahwa input tidak berubah, output terurut dan saling lepas, serta hasil acak cocok dengan implementasi referensi yang lambat.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah ini interval tertutup atau setengah terbuka, dan apakah titik akhir bersama ikut digabungkan? Interval di sini tertutup, jadi kondisinya adalah next_start <= current_end. Jika produk memperlakukan kedekatan/ketetanggaan secara terpisah, gunakan perbandingan ketat. Untuk [a, b), apakah rentang yang bersambungan tetapi tidak tumpang tindih digabungkan merupakan pilihan terpisah.
• Apakah input sudah terurut berdasarkan start? Input yang sudah terurut hanya memerlukan pemindaian linear, mengurangi waktu menjadi O(n). Input yang belum terurut memerlukan pengurutan atau metode khusus yang terikat pada domain titik akhir yang terbatas.
• Bolehkah saya memutasi input? Jika ya, urutkan di tempat (in-place) dan padatkan dengan pointer tulis. Jika tidak, salin datanya atau gunakan operasi pengurutan yang mengembalikan daftar baru.
• Apakah titik akhir berupa bilangan bulat dari rentang terbatas yang kecil? Pengurutan berbasis perbandingan adalah pilihan langsung untuk nilai arbitrer yang dapat dibandingkan. Semesta bilangan bulat kecil memungkinkan penggunaan bucket atau larik selisih (difference array), tetapi biayanya bergantung pada rentang koordinat daripada hanya pada n.
• Apakah ini satu kali penggabungan offline atau aliran (stream) yang berkelanjutan? Aliran yang terurut berdasarkan start dapat digabungkan dan dikeluarkan secara daring (online). Aliran dengan urutan arbitrer tidak dapat difinalisasi lebih awal dengan aman karena interval di masa mendatang mungkin dimulai lebih awal dan menjembatani komponen yang ada.
• Apakah output hanya membutuhkan batas, atau harus mempertahankan metadata interval? Menggabungkan batas tidak mendefinisikan bagaimana label, izin, atau harga digabungkan. Metadata membutuhkan aturan agregasi yang eksplisit.

Kerangka Jawaban 30 Detik

"Pertama-tama saya akan mengonfirmasi bahwa ini adalah interval tertutup, titik akhir bersama dihitung sebagai tumpang tindih, dan saya tidak boleh memutasi input. Saya akan menyalin dan mengurutkan berdasarkan start dan end, lalu mempertahankan satu interval gabungan saat ini. Jika start berikutnya berada pada atau sebelum end saat ini, saya memperluas end ke nilai maksimum dari kedua end tersebut. Jika tidak, tidak ada interval berikutnya yang dapat menjangkau interval saat ini, jadi saya menambahkannya ke hasil dan memulai rentang baru. Saya menambahkan rentang terakhir setelah pemindaian selesai. Pengurutan memakan biaya O(n log n), pemindaian memakan biaya O(n), dan salinan terurut beserta output menggunakan ruang O(n). Invarian kebenarannya adalah bahwa interval yang dikeluarkan sudah final dan interval saat ini merupakan komponen terhubung terakhir yang belum dikeluarkan."

Pembahasan Mendalam Langkah-demi-Langkah

Pendekatan langsung berulang kali mencari pasangan yang tumpang tindih, menggantinya dengan gabungannya, dan memulai ulang sampai tidak ada lagi yang berubah. Pendekatan ini mudah diungkapkan dengan loop bersarang, tetapi interval yang baru digabungkan mungkin tumpang tindih dengan sesuatu yang sudah diperiksa sebelumnya, sehingga dapat memerlukan banyak putaran pemindaian dan mencapai O(n²) atau lebih buruk. Metode tersebut berguna sebagai uji oracle untuk input kecil, tetapi merupakan solusi utama yang buruk.

Pengurutan mengubah masalah global menjadi pemindaian dari kiri ke kanan. Urutkan berdasarkan (start, end) secara menaik. Pertahankan current = [current_start, current_end], komponen gabungan akhir di antara interval yang diproses yang belum dikeluarkan. Untuk setiap [start, end] berikutnya:

1. Jika start <= current_end, kedua interval tertutup saling tumpang tindih, jadi setel current_end menjadi max(current_end, end).
2. Jika start > current_end, terdapat celah. Setiap start berikutnya bernilai setidaknya start, sehingga tidak ada interval mendatang yang dapat menjangkau current. Keluarkan interval tersebut dan mulai interval baru.

Pemindaian mempertahankan tiga invarian:

1. Interval yang dikeluarkan terurut, saling lepas, dan tidak akan pernah berubah.
2. Gabungan dari interval yang dikeluarkan dan current sama dengan gabungan dari semua interval input yang telah diproses.
3. current adalah komponen gabungan maksimal terakhir di antara interval yang telah diproses dan satu-satunya komponen yang dapat tumpang tindih dengan interval berikutnya.

Ketiganya berlaku setelah inisialisasi dari interval pertama yang terurut. Tumpang tindih hanya memperluas titik akhir kanan dari komponen terakhir dan mempertahankan gabungannya. Pada celah, pengurutan menjamin bahwa setiap start di masa mendatang berada di luar current_end, sehingga pengeluaran interval aman dilakukan. Berdasarkan induksi, invarian berlaku selama pemindaian. Mengeluarkan current sekali lagi di bagian akhir menghasilkan gabungan yang ekuivalen di mana tidak ada lagi pasangan yang dapat digabungkan lebih lanjut.

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() membangun daftar terurut yang baru, dan pembongkaran tuple tidak menulis ulang daftar dalam yang asli, sehingga fungsi mematuhi kontrak non-mutasinya. Pengurutan perbandingan memakan biaya O(n log n) dan pemindaian memakan biaya O(n), menghasilkan O(n log n) secara keseluruhan. Salinan terurut dan output yang mungkin berisi semua interval n keduanya linear, sehingga ruang termasuk output adalah O(n). Jika input sudah terurut, melewati proses pengurutan memberikan waktu O(n). Jika mutasi diizinkan, pengurutan di tempat dan pointer tulis dapat menggunakan kembali input, meskipun implementasi pengurutan mungkin masih memerlukan ruang stack atau buffer.

Validasi harus mencakup input kosong, satu interval, semua interval saling lepas, titik akhir bersama, cakupan penuh, duplikat, titik akhir negatif, dan tumpang tindih berantai. Misalnya, [[1, 2], [2, 3], [3, 4]] harus menjadi [[1, 4]]; ini menangkap kode yang hanya membandingkan interval mentah yang berdekatan. Simpan salinan mendalam (deep copy) dan pastikan bahwa pemanggilan fungsi tidak mengubahnya. Kemudian buat input acak kecil dan bandingkan dengan oracle lambat yang berulang kali menggabungkan pasangan yang tumpang tindih. Implementasi di atas telah diuji secara diferensial pada 10.000 kasus acak dengan seed tetap.

Untuk nilai arbitrer dalam model perbandingan, urutkan dan pindai adalah jawaban umum yang jelas. Ketika n sangat kecil, penggabungan pasangan berulang mungkin lebih pendek dan batas waktunya yang lebih lambat mungkin tidak masalah. Input yang sudah terurut hanya memerlukan pemindaian. Domain bilangan bulat terbatas yang kecil dapat membenarkan penggunaan bucket atau teknik larik selisih yang biayanya bergantung pada semesta koordinat. Dalam wawancara, perkenalkan kasus-kasus khusus tersebut hanya setelah batasan masalah membenarkannya.

Contoh Jawaban Berkualitas Tinggi

"Pertama-tama saya akan memperjelas batasannya: input berisi interval tertutup yang belum terurut, berbagi titik akhir dihitung sebagai tumpang tindih, dan saya harus mengembalikan data baru. Itu berarti [1, 4] dan [4, 5] menggunakan pengujian kurang-dari-atau-sama-dengan.

Versi brute-force dapat terus mencari pasangan dan memulai ulang, tetapi interval yang baru digabungkan dapat tumpang tindih dengan sesuatu yang terlihat sebelumnya, sehingga mungkin memerlukan banyak putaran. Saya akan mengurutkan berdasarkan start dan hanya menyimpan satu interval yang belum final. Ketika start berikutnya berada di dalam batas end-nya, saya memperluasnya dengan end yang lebih besar. Jika tidak, saya menulisnya ke hasil dan memulai komponen baru.

Perbandingan penting dilakukan terhadap komponen yang terakumulasi, bukan hanya interval mentah sebelumnya. Pengurutan menjamin bahwa begitu start berikutnya melebihi end saat ini, setiap start berikutnya juga akan melebihi, sehingga hasil saat ini bersifat final secara permanen. Oleh karena itu, prefiks yang dikeluarkan tetap terurut dan saling lepas, sementara interval saat ini mencakup persis komponen gabungan terakhir dari input yang telah diproses.

Saya akan menggunakan sorted() untuk menghindari pengubahan daftar milik pemanggil dan segera mengembalikan hasil jika input kosong. Waktunya adalah O(n log n) untuk pengurutan ditambah pemindaian linear, dan salinan terurut beserta output menggunakan ruang O(n). Saya akan menguji interval yang bersentuhan, bersarang, duplikat, negatif, dan berantai, lalu melakukan uji diferensial terhadap penggabungan berpasangan yang lambat sambil memastikan bahwa input tidak berubah."

Kesalahan Umum

• Memilih < atau <= tanpa mendefinisikan semantik titik akhir → hasil titik akhir bersama bergantung pada kontrak → Nyatakan semantik tertutup versus setengah terbuka dan apakah rentang yang bersambungan digabungkan sebelum memilih kondisi.
• Memindai dalam urutan asli → interval yang tumpang tindih mungkin berjauhan dan interval di masa mendatang dapat menyambungkan kembali output yang telah dikeluarkan → Urutkan berdasarkan start, kecuali jika input yang terurut dijamin.
• Hanya membandingkan interval mentah yang berdekatan → elemen ketiga dalam [1, 10], [2, 3], [9, 12] harus bertemu dengan [1, 10] yang telah diperluas → Selalu bandingkan dengan hasil gabungan terakhir.
• Menetapkan current_end = end saat tumpang tindih → interval yang tercakup di dalamnya akan menyusutkan rentang yang dicakup → Gunakan max(current_end, end).
• Lupa menambahkan elemen terakhir (final append) → loop yang hanya mengeluarkan saat ada celah akan kehilangan komponen terakhir → Tambahkan current sekali setelah loop selesai.
• Membaca elemen pertama untuk input kosong → inisialisasi akan memunculkan error indeks → Kembalikan daftar kosong sebelum pengurutan dan inisialisasi.
• Menjanjikan tanpa mutasi tetapi mengurutkan di tempat → pemanggil melihat input yang urutannya berubah, dan daftar dalam yang digunakan kembali dapat terus berubah → Gunakan sorted() dan objek hasil baru, atau jadikan mutasi sebagai bagian dari kontrak.
• Hanya menguji larik yang diharapkan → tumpang tindih berantai, mutasi, dan kesalahan batas bisa tetap tersembunyi → Tambahkan pemeriksaan properti dan uji oracle diferensial acak.
• Mengklaim O(n log n) selalu tidak dapat dihindari → input yang terurut dan domain bilangan bulat terbatas yang kecil dapat menghindari pengurutan perbandingan → Batasi klaim batas bawah hanya untuk titik akhir arbitrer yang belum terurut dan dapat dibandingkan.

Pertanyaan Lanjutan dan Cara Menanganinya

Pertanyaan Lanjutan 1: Apa yang berubah jika titik akhir bersama tidak dihitung sebagai tumpang tindih?

Ubah kondisinya dari start <= current_end menjadi start < current_end. Konfirmasikan bahasa domainnya terlebih dahulu: interval tertutup yang berbagi titik akhir memang berpotongan secara matematis, sehingga produk yang memisahkannya sebenarnya meminta untuk menggabungkan hanya tumpang tindih dengan panjang positif. Untuk [a, b) setengah terbuka, [1, 4) dan [4, 5) tidak tumpang tindih; penggabungan rentang yang bersambungan kemudian menjadi aturan independen lainnya.

Pertanyaan Lanjutan 2: Input sudah terurut dan mutasi diizinkan. Bagaimana Anda dapat mengurangi ruang ekstra?

Lewati pengurutan dan padatkan ke dalam prefiks input dengan pointer tulis. Pointer baca memeriksa interval baru. Saat tumpang tindih, perbarui end pada posisi tulis; saat ada celah, majukan pointer tulis dan salin interval baru. Kembalikan panjang prefiks atau tampilan (view) dari prefiks tersebut. Pemindaian memakan waktu O(n) dan ruang bantu O(1) di luar representasi yang dikembalikan, dengan konsekuensi merusak input asli.

Pertanyaan Lanjutan 3: Interval tiba terus menerus dalam urutan start. Bisakah Anda mengeluarkan aliran (stream)?

Bisa. Pertahankan hanya current. Saat start yang tiba melebihi end-nya, keluarkan current dan mulai komponen berikutnya; keluarkan komponen terakhir saat aliran ditutup. Memori kerja adalah O(1) di luar output. Dengan urutan kedatangan arbitrer, interval di masa mendatang dapat menjembatani dua komponen, sehingga pengeluaran lebih awal tidak aman. Sebagai gantinya, lakukan buffering, urutkan secara eksternal, atau pertahankan struktur interval dinamis.

Pertanyaan Lanjutan 4: Bagaimana jika seratus juta interval tidak muat dalam memori?

Gunakan pengurutan eksternal berdasarkan start: urutkan batch seukuran memori ke dalam run yang terurut, lalu lakukan k-way merge. Aliran penggabungan sudah terurut berdasarkan start, jadi jalankan state machine satu interval yang sama saat menggabungkan alih-alih mematerialisasi file lengkap yang terurut secara global terlebih dahulu. Pekerjaan perbandingan tetap pada urutan O(n log n); I/O disk dan penyimpanan sementara menjadi biaya tambahan yang penting.

Pertanyaan Lanjutan 5: Bisakah interval dengan harga atau label izin digabungkan secara langsung?

Hanya batas geometrisnya yang dapat digabungkan oleh algoritma ini. Jika segmen yang tumpang tindih memiliki label yang berbeda, menggabungkannya menjadi satu label akan menghilangkan informasi. Tentukan apakah output membawa sekumpulan label, label dengan prioritas tertinggi, atau subsegmen minimal tempat metadata bersifat konstan. Pilihan terakhir biasanya memerlukan pemindaian menyapu (sweep) atas peristiwa titik akhir daripada penggabungan interval sederhana.