Cantumkan Selang yang Bertindih
Gabungkan julat yang bersentuhan atau bertindih.
Cantumkan Selang yang Bertindih ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Matlamat Penggabungan
Diberikan banyak selang, Anda mahu menggabungkan selang yang bersentuhan atau bertindih menjadi julat tidak bertindih yang paling sedikit. 🧩
Apabila Dua Selang Bertindih
Dua selang bertindih apabila satu selang bermula sebelum selang yang satu lagi berakhir. Selepas mengisih mengikut permulaan, ini bermaksud permulaan seterusnya adalah pada atau sebelum pengakhiran semasa.
Sentiasa Isih Dahulu
Penggabungan hanya berfungsi dari kiri ke kanan jika selang berada dalam susunan yang betul, jadi mulakan dengan mengisihnya mengikut permulaan. Inilah asas keseluruhan imbasan.
intervals.sort(key=lambda x: x[0])Simpan Julat Semasa
Telusuri senarai yang telah diisih sambil menyimpan satu selang gabungan semasa. Setiap selang baharu sama ada memanjangkannya atau memulakan julat baharu.
Panjangkan Apabila Bertindih
Jika permulaan seterusnya berada dalam julat semasa, kedua-duanya bertindih, jadi Anda perlu memanjangkan pengakhiran semasa kepada nilai yang lebih besar antara kedua-dua pengakhiran.
cur_end = max(cur_end, end)Ambil Pengakhiran Maksimum
Sentiasa gunakan nilai maksimum untuk pengakhiran baharu. Selang pendek yang berada di dalam selang panjang tidak boleh mengecilkan julat yang telah Anda bina.
Tutup dan Buka yang Baharu
Jika permulaan seterusnya melepasi pengakhiran semasa, terdapat jurang. Masukkan julat yang telah selesai ke dalam jawapan dan mulakan selang semasa yang baharu.
result.append([cur_start, cur_end])Jangan Lupakan yang Terakhir
Gelung membina julat terakhir tetapi tidak pernah memasukkannya. Selepas gelung tamat, append selang semasa terakhir itu supaya tidak hilang.
Sentuhan Dikira sebagai Pertindihan
Tentukan sama ada [1, 3] dan [3, 5] perlu digabungkan. Biasanya, kedua-duanya perlu digabungkan, jadi gunakan start <= cur_end. Baca pernyataan masalah untuk mengesahkan peraturan kes pinggir ini.
Imbasan Penuh
Satu laluan selepas sort memberikan semua selang yang telah digabungkan, jadi keseluruhan kaedah berjalan dalam O(n log n) hasil daripada sort serta imbasan 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, eKegunaan Lazim
Penggabungan menjadi asas kepada kalendar dan sistem tempahan: gabungkan blok sibuk untuk melihat masa lapang sebenar. Banyak tugasan pertandingan menyembunyikan bentuk yang sama ini.
Semakan Pantas
Anda menggabungkan selang selepas sort berdasarkan masa mula.
Ringkasan
Sort berdasarkan masa mula, simpan julat semasa, dan panjangkan dengan nilai maksimum apabila bertindih, atau masukkan dan tetapkan semula apabila terdapat jurang. Jangan lupa append yang terakhir. 🚀
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Cantumkan Selang yang Bertindih” percuma?
Ya — teks penuh “Cantumkan Selang yang Bertindih” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Cantumkan Selang yang Bertindih”?
Gabungkan julat yang bersentuhan atau bertindih. Anda berlatih Competitive Programming Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Cantumkan Selang yang Bertindih” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Isih Selang Mengikut Mula
- Cantumkan Selang yang Bertindih
- Sapuan Garis untuk Pertindihan Maksimum
- Pengalihan Minimum untuk Tiada Pertindihan