0Pricing
Competitive Programming Academy · Pelajaran

Menggabungkan Interval yang Tumpang Tindih

Menggabungkan rentang yang bersentuhan atau tumpang tindih

Menggabungkan Interval yang Tumpang Tindih adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Tujuan Penggabungan

Diberikan banyak interval, Anda ingin menggabungkan interval yang bersentuhan atau tumpang tindih menjadi sesedikit mungkin rentang yang tidak saling tumpang tindih. 🧩

Kapan Dua Interval Tumpang Tindih

Dua interval tumpang tindih ketika salah satunya dimulai sebelum interval lainnya berakhir. Setelah diurutkan berdasarkan awal, artinya awal berikutnya kurang dari atau sama dengan akhir saat ini.

Selalu Urutkan Terlebih Dahulu

Penggabungan hanya dapat dilakukan dari kiri ke kanan jika interval sudah berurutan, jadi mulailah dengan mengurutkan interval berdasarkan awal. Inilah dasar seluruh penelusuran.

intervals.sort(key=lambda x: x[0])

Pertahankan Rentang Saat Ini

Telusuri daftar yang telah diurutkan sambil menyimpan satu interval hasil penggabungan saat ini. Setiap interval baru akan memperluasnya atau memulai rentang baru.

Perluas Saat Tumpang Tindih

Jika awal berikutnya berada di dalam rentang saat ini, keduanya tumpang tindih, jadi perpanjang akhir saat ini hingga nilai yang lebih besar dari kedua akhir tersebut.

cur_end = max(cur_end, end)

Ambil Akhir Maksimum

Selalu gunakan nilai maksimum untuk akhir yang baru. Interval pendek yang berada di dalam interval panjang tidak boleh memperkecil rentang yang telah Anda buat.

Tutup dan Buka yang Baru

Jika awal berikutnya melewati akhir saat ini, terdapat celah. Masukkan rentang yang telah selesai ke jawaban Anda dan mulai interval saat ini yang baru.

result.append([cur_start, cur_end])

Jangan Lupakan yang Terakhir

Perulangan membangun rentang terakhir, tetapi tidak pernah memasukkannya. Setelah perulangan berakhir, append interval saat ini yang terakhir agar tidak hilang.

Sentuhan Dianggap sebagai Tumpang Tindih

Tentukan apakah [1, 3] dan [3, 5] harus digabungkan. Biasanya, ya, jadi gunakan start <= cur_end. Baca soal untuk memastikan aturan batas ini.

Penyapuan Penuh

Satu kali lintasan setelah pengurutan memberi Anda semua rentang yang telah digabungkan, sehingga seluruh metode berjalan dalam O(n log n) dari sort ditambah penyapuan linear.

for s, e in intervals[1:]:
    if s <= cur_end:
        cur_end = max(cur_end, e)
    else:
        result.append([cur_start, cur_end]); cur_start, cur_end = s, e

Penggunaan Umum

Penggabungan mendukung kalender dan sistem pemesanan: ringkas blok sibuk untuk melihat waktu luang yang sebenarnya. Banyak soal pemrograman kompetitif menyamarkan pola yang sama.

Pemeriksaan Cepat

Anda menggabungkan interval setelah mengurutkannya berdasarkan waktu mulai.

Ringkasan

Urutkan berdasarkan waktu mulai, simpan rentang saat ini, lalu perluas dengan nilai maksimum saat terjadi tumpang tindih, atau masukkan dan mulai ulang saat ada celah. Ingat append terakhir. 🚀

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Menggabungkan Interval yang Tumpang Tindih” gratis?

Ya — teks lengkap “Menggabungkan Interval yang Tumpang Tindih” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Menggabungkan Interval yang Tumpang Tindih”?

Menggabungkan rentang yang bersentuhan atau tumpang tindih Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?

Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.

Berapa lama pelajaran “Menggabungkan Interval yang Tumpang Tindih” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?

Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Mengurutkan Interval Berdasarkan Awal
  2. Menggabungkan Interval yang Tumpang Tindih
  3. Line Sweep untuk Tumpang Tindih Maksimum
  4. Penghapusan Minimum agar Tidak Tumpang Tindih
← Kembali ke Competitive Programming Academy