LeetCode 57: Menyisipkan Interval – Panduan Komprehensif dengan Contoh dan Optimasi

Pendahuluan

Selamat datang di panduan mendalam tentang masalah LeetCode 57, “Menyisipkan Interval.” Masalah ini adalah soal klasik dalam kategori interval yang menguji pemahaman Anda tentang manipulasi interval, penggabungan, dan efisiensi algoritma. Dalam postingan blog ini, kita akan menjelajahi masalah ini secara mendalam, menyediakan penjelasan langkah demi langkah, beberapa solusi dengan kode Python, analisis kompleksitas waktu dan ruang, dan tips untuk optimasi. Pada akhir tutorial ini, Anda akan memiliki pemahaman yang kuat tentang cara mengatasi masalah ini dan masalah interval serupa.

Memahami Masalahnya

Pernyataan Masalah

Anda diberikan daftar interval non-tumpang tindih yang diurutkan menurut awal interval. Anda juga diberikan interval baru. Sisipkan interval baru ke dalam interval (gabungkan jika perlu).

Contoh

1. Contoh 1:
   Interval: [1,3],[6,9], sisipkan dan gabungkan (jika perlu) [2,5].
   Keluaran: [1,5],[6,9]
2. Contoh 2:
   Interval: [1,2],[3,5],[6,7],[8,10],[12,16], sisipkan dan gabungkan (jika perlu) [4,8].
   Keluaran: [1,2],[3,10],[12,16]
   Penjelasan: Karena interval baru [4,8] tumpang tindih dengan [3,5],[6,7],[8,10].
3. Contoh 3:
   Interval: [], sisipkan dan gabungkan (jika perlu) [5,7].
   Keluaran: [5,7]
4. Contoh 4:
   Interval: [1,5], sisipkan dan gabungkan (jika perlu) [2,3].
   Keluaran: [1,5]

Batasan

• 0 <= interval.length <= 104
• interval[i].length == 2
• 0 <= interval[i][0] <= interval[i][1] <= 105
• interval diurutkan dalam urutan menaik berdasarkan interval[i][0]
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 105

Pendekatan

Masalah ini dapat diselesaikan secara efisien dengan iterasi sekali melalui daftar interval yang ada, membandingkan interval baru dengan masing-masing interval yang ada, dan menggabungkannya jika perlu. Berikut adalah pendekatan umum:

1. Inisialisasi: Buat daftar hasil untuk menyimpan interval yang digabungkan.
2. Iterasi: Iterasi melalui interval yang ada.
3. Kasus Non-Tumpang Tindih: Jika interval baru terletak sebelum interval saat ini (tidak ada tumpang tindih), tambahkan interval baru ke hasil dan perbarui interval baru ke interval saat ini.
4. Kasus Non-Tumpang Tindih: Jika interval baru terletak setelah interval saat ini (tidak ada tumpang tindih), tambahkan interval saat ini ke hasil.
5. Kasus Tumpang Tindih: Jika interval baru tumpang tindih dengan interval saat ini, gabungkan interval baru dengan interval saat ini dan perbarui interval baru.
6. Sisipkan: Setelah iterasi melalui semua interval yang ada, tambahkan interval baru terakhir (yang mungkin telah digabungkan beberapa kali) ke hasil.
7. Kembalikan: Kembalikan daftar hasil.

Solusi Python

Berikut adalah beberapa solusi Python untuk masalah Menyisipkan Interval:

Solusi 1: Pendekatan Iteratif

Pendekatan ini secara iteratif melalui interval yang ada, menggabungkan interval baru saat dibutuhkan.

def insert(intervals, newInterval):
    result = []
    i = 0

    # Tambahkan semua interval yang berakhir sebelum newInterval dimulai
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Gabungkan semua interval yang tumpang tindih dengan newInterval
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    # Tambahkan interval yang digabungkan
    result.append(newInterval)

    # Tambahkan sisa interval
    while i < len(intervals):
        result.append(intervals[i])
        i += 1

    return result
  

Penjelasan

1. Inisialisasi:
   • result = []: Buat daftar kosong untuk menyimpan interval yang digabungkan.
   • i = 0: Inisialisasi indeks untuk melakukan iterasi melalui interval yang ada.
2. Menambahkan Interval Non-Tumpang Tindih Awal:
   • while i < len(intervals) and intervals[i][1] < newInterval[0]:: Loop melalui interval sebanyak mungkin yang berakhir sebelum newInterval dimulai.
   • result.append(intervals[i]): Tambahkan interval-interval ini ke daftar result karena mereka tidak tumpang tindih dengan newInterval.
   • i += 1: Naikkan indeks.
3. Menggabungkan Interval Tumpang Tindih:
   • while i < len(intervals) and intervals[i][0] <= newInterval[1]:: Loop selama masih ada interval dan interval saat ini dimulai sebelum newInterval berakhir (menunjukkan tumpang tindih).
   • newInterval[0] = min(newInterval[0], intervals[i][0]): Sesuaikan awal newInterval ke nilai minimum awal antara newInterval dan interval saat ini.
   • newInterval[1] = max(newInterval[1], intervals[i][1]): Sesuaikan akhir newInterval ke nilai maksimum akhir antara newInterval dan interval saat ini.
   • i += 1: Naikkan indeks.
4. Menambahkan Interval yang Digabungkan:
   • result.append(newInterval): Setelah penggabungan, tambahkan newInterval yang digabungkan ke daftar result.
5. Menambahkan Interval Non-Tumpang Tindih Sisa:
   • while i < len(intervals):: Loop melalui interval yang tersisa.
   • result.append(intervals[i]): Tambahkan interval-interval ini ke daftar result karena mereka tidak tumpang tindih dengan newInterval.
   • i += 1: Naikkan indeks.
6. Mengembalikan Hasil:
   • return result: Kembalikan daftar result yang berisi interval yang digabungkan.

Contoh Penggunaan

intervals = [[1,3],[6,9]]
newInterval = [2,5]
print(insert(intervals, newInterval))  # Keluaran: [[1, 5], [6, 9]]

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
print(insert(intervals, newInterval))  # Keluaran: [[1, 2], [3, 10], [12, 16]]

intervals = []
newInterval = [5,7]
print(insert(intervals, newInterval))  # Keluaran: [[5, 7]]

intervals = [[1,5]]
newInterval = [2,3]
print(insert(intervals, newInterval))  # Keluaran: [[1, 5]]
  

Solusi 2: Kode Lebih Singkat dan Lebih Mudah Dibaca

Ini adalah versi yang lebih ringkas dari solusi sebelumnya, tetapi mempertahankan logika yang sama.

def insert_compact(intervals, newInterval):
    merged = []
    i = 0
    # Tambahkan interval yang tidak tumpang tindih sebelum newInterval
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1

    # Gabungkan interval yang tumpang tindih
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    merged.append(newInterval)

    # Tambahkan sisa interval yang tidak tumpang tindih
    while i < len(intervals):
        merged.append(intervals[i])
        i += 1

    return merged
  

Penjelasan

1. Inisialisasi:
   • merged = []: Buat daftar kosong untuk menyimpan interval yang digabungkan.
   • i = 0: Inisialisasi indeks untuk iterasi melalui interval.
2. Menambahkan Interval Non-Tumpang Tindih Awal:
   • while i < len(intervals) and intervals[i][1] < newInterval[0]:: Tambahkan semua interval yang berakhir sebelum newInterval dimulai.
   • merged.append(intervals[i]): Tambahkan interval ini ke daftar merged.
   • i += 1: Naikkan indeks.
3. Menggabungkan Interval Tumpang Tindih:
   • while i < len(intervals) and intervals[i][0] <= newInterval[1]:: Gabungkan semua interval yang tumpang tindih dengan newInterval.
   • newInterval[0] = min(newInterval[0], intervals[i][0]): Perbarui awal newInterval.
   • newInterval[1] = max(newInterval[1], intervals[i][1]): Perbarui akhir newInterval.
   • i += 1: Naikkan indeks.
4. Menambahkan Interval yang Digabungkan:
   • merged.append(newInterval): Tambahkan interval yang digabungkan.
5. Menambahkan Interval Non-Tumpang Tindih Sisa:
   • while i < len(intervals):: Tambahkan interval yang tersisa.
   • merged.append(intervals[i]): Tambahkan interval ini ke daftar merged.
   • i += 1: Naikkan indeks.
6. Mengembalikan Hasil:
   • return merged: Kembalikan daftar yang digabungkan.

Contoh Penggunaan

intervals = [[1,3],[6,9]]
newInterval = [2,5]
print(insert_compact(intervals, newInterval))  # Keluaran: [[1, 5], [6, 9]]

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
print(insert_compact(intervals, newInterval))  # Keluaran: [[1, 2], [3, 10], [12, 16]]

intervals = []
newInterval = [5,7]
print(insert_compact(intervals, newInterval))  # Keluaran: [[5, 7]]

intervals = [[1,5]]
newInterval = [2,3]
print(insert_compact(intervals, newInterval))  # Keluaran: [[1, 5]]
  

Solusi 3: Pendekatan dengan Memisahkan Logika

Pendekatan ini memisahkan logika menjadi tiga bagian: interval sebelum tumpang tindih, interval tumpang tindih, dan interval setelah tumpang tindih. Ini membuatnya lebih mudah dibaca dan dipahami.

def insert_separated(intervals, newInterval):
    before = []
    overlap = []
    after = []

    for interval in intervals:
        if interval[1] < newInterval[0]:
            before.append(interval)
        elif interval[0] > newInterval[1]:
            after.append(interval)
        else:
            overlap.append(interval)

    if not overlap:
        return before + [newInterval] + after

    merged_interval = [min(newInterval[0], overlap[0][0]), max(newInterval[1], overlap[-1][1])]
    return before + [merged_interval] + after
  

Penjelasan

1. Inisialisasi:
   • before = []: Daftar interval yang sepenuhnya sebelum interval baru.
   • overlap = []: Daftar interval yang tumpang tindih dengan interval baru.
   • after = []: Daftar interval yang sepenuhnya setelah interval baru.
2. Pengelompokan Interval:
   • Loop melalui setiap interval dalam daftar intervals:
     • Jika interval[1] < newInterval[0]: interval berakhir sebelum interval baru dimulai, jadi tambahkan ke before.
     • Jika interval[0] > newInterval[1]: interval dimulai setelah interval baru berakhir, jadi tambahkan ke after.
     • Jika tidak, interval tumpang tindih dengan interval baru, jadi tambahkan ke overlap.
3. Menangani Tidak Ada Tumpang Tindih:
   • Jika overlap kosong, tidak ada interval yang tumpang tindih dengan interval baru.
   • Kembalikan before + [newInterval] + after: gabungkan daftar before, interval baru, dan daftar after.
4. Menggabungkan Interval Tumpang Tindih:
   • Jika overlap tidak kosong, gabungkan interval yang tumpang tindih menjadi satu interval:
     • merged_interval = [min(newInterval[0], overlap[0][0]), max(newInterval[1], overlap[-1][1])]: buat interval baru yang dimulai dari awal terkecil dan berakhir di akhir terbesar dari interval tumpang tindih.
   • Kembalikan before + [merged_interval] + after: gabungkan daftar before, interval yang digabungkan, dan daftar after.

Contoh Penggunaan

intervals = [[1,3],[6,9]]
newInterval = [2,5]
print(insert_separated(intervals, newInterval))  # Keluaran: [[1, 5], [6, 9]]

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
print(insert_separated(intervals, newInterval))  # Keluaran: [[1, 2], [3, 10], [12, 16]]

intervals = []
newInterval = [5,7]
print(insert_separated(intervals, newInterval))  # Keluaran: [[5, 7]]

intervals = [[1,5]]
newInterval = [2,3]
print(insert_separated(intervals, newInterval))  # Keluaran: [[1, 5]]
  

Analisis Kompleksitas

Kompleksitas Waktu

Ketiga solusi memiliki kompleksitas waktu O(n), di mana n adalah jumlah interval dalam daftar input. Ini karena kita melakukan iterasi melalui daftar interval paling banyak tiga kali dalam kasus terburuk.

Kompleksitas Ruang

Kompleksitas ruang dari solusi ini adalah O(n) juga, dalam kasus terburuk. Ini karena kita membuat daftar baru untuk menyimpan interval yang digabungkan, yang dalam kasus terburuk dapat berisi semua interval dari input.

Optimasi

Meskipun solusinya sudah cukup efisien, ada beberapa optimasi kecil yang dapat Anda pertimbangkan:

• Modifikasi di Tempat: Jika Anda diizinkan untuk memodifikasi daftar input secara langsung, Anda dapat menghindari kebutuhan untuk membuat daftar baru, mengurangi kompleksitas ruang menjadi O(1). Namun, ini akan mengubah daftar input asli.
• Penggabungan Lebih Awal: Dalam loop penggabungan, Anda dapat menambahkan pemeriksaan tambahan untuk memutuskan apakah perlu terus menggabungkan interval. Jika newInterval tidak berubah setelah iterasi, Anda dapat memecah loop lebih awal.

Tips Pemecahan Masalah

Saat mengatasi masalah seperti ini, berikut adalah beberapa tips yang perlu diingat:

• Kasus Edge: Selalu pertimbangkan kasus edge seperti daftar input kosong, interval baru yang tumpang tindih dengan semua interval yang ada, atau interval baru yang tidak tumpang tindih dengan interval apa pun.
• Visualisasi: Gambarlah contoh-contoh di atas kertas untuk memvisualisasikan proses penggabungan. Ini dapat membantu Anda memahami logika dan mengidentifikasi potensi kesalahan.
• Pengujian: Uji solusi Anda dengan berbagai kasus uji, termasuk kasus edge dan kasus umum, untuk memastikan bahwa solusinya benar.

Perbandingan Solusi

Berikut adalah perbandingan singkat dari ketiga solusi:

Semua solusi menawarkan kompleksitas waktu dan ruang yang serupa, tetapi pilihan terbaik Anda bergantung pada preferensi pribadi dan kebutuhan keterbacaan. Pendekatan dengan memisahkan logika (Solusi 3) menawarkan keterbacaan yang lebih baik, sementara pendekatan iteratif (Solusi 1 dan 2) lebih ringkas.

Aplikasi Dunia Nyata

Konsep penggabungan interval memiliki aplikasi praktis di berbagai bidang:

• Penjadwalan: Mengoptimalkan jadwal rapat atau alokasi sumber daya dengan menggabungkan interval waktu.
• Manajemen Acara: Mengelola pendaftaran acara dan penjadwalan sesi.
• Sistem Basis Data: Mengoptimalkan kueri rentang data.
• Grafik: Memproses rentang yang tumpang tindih dalam representasi visual.

Kesimpulan

Masalah LeetCode 57, Menyisipkan Interval, adalah latihan yang sangat baik untuk menguasai manipulasi interval dan algoritma penggabungan. Dalam postingan blog ini, kita telah menjelajahi masalah ini secara mendalam, membahas pendekatan langkah demi langkah, menyediakan beberapa solusi Python, menganalisis kompleksitas waktu dan ruang, dan memberikan tips optimasi. Dengan memahami konsep-konsep ini dan mempraktikkannya, Anda akan lebih siap untuk mengatasi masalah interval yang serupa dan meningkatkan keterampilan pemecahan masalah Anda.

Ingatlah untuk selalu mempertimbangkan batasan masalah, kasus edge, dan potensi optimasi saat mengerjakan masalah algoritma. Selamat membuat kode!