Sapuan Garis untuk Pertindihan Maksimum
Kira selang serentak dengan peristiwa.
Sapuan Garis untuk Pertindihan Maksimum ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 3 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.
Soalan Pertindihan Maksimum
Berapakah bilangan selang yang meliputi saat yang sama? Bilangan puncak ialah pertindihan maksimum, iaitu titik paling sibuk pada garis masa anda. 📈
Fikirkan Peristiwa
Jangan lagi fikirkan selang secara keseluruhan. Bahagikan setiap selang kepada dua peristiwa: +1 apabila ia bermula dan -1 apabila ia berakhir.
Bina Senarai Peristiwa
Untuk setiap selang, tambahkan satu peristiwa mula dan satu peristiwa tamat ke dalam satu senarai dikongsi. Setiap peristiwa membawa kedudukan dan perubahan tambah satu atau tolak satu.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Sort Peristiwa
Sort setiap peristiwa mengikut kedudukan supaya anda boleh mengimbas garis masa dari kiri ke kanan dan memproses perubahan dalam susunan yang betul.
events.sort()Imbas dan Kira
Telusuri peristiwa yang telah disusun sambil mengekalkan pembilang berjalan. Tambahkan setiap perubahan semasa anda melepasinya, dan pembilang itu menunjukkan bilangan selang yang aktif sekarang.
active = 0
for pos, delta in events:
active += deltaJejaki Puncak
Selepas setiap kemas kini, bandingkan pembilang dengan nilai terbaik anda setakat ini. Nilai terbesar yang pernah dicapai oleh pembilang ialah pertindihan maksimum.
best = max(best, active)Helah Pemutus Seri
Pada kedudukan yang sama, susunan adalah penting. Jika selang yang tamat pada x sepatutnya membebaskan ruang sebelum selang yang bermula pada x, susun selang tamat sebelum selang mula pada titik yang sama.
Kodkan Perubahan untuk Diisih dengan Betul
Satu cara yang kemas untuk memutuskan seri ialah memilih perubahan supaya sort tupel melakukannya untuk anda. Letakkan perubahan -1 sebelum +1 apabila kedudukannya sama.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieSebab Ia Pantas
Anda mencipta 2n peristiwa, sort sekali dan mengimbas sekali. Keseluruhan kaedah ialah O(n log n), dengan kos utama datang daripada satu sort tersebut.
Tempat Anda Menemuinya
Pertindihan maksimum menjawab tugasan klasik seperti bilangan minimum bilik yang diperlukan untuk mesyuarat, atau bilangan pengguna serentak yang memuncak pada pelayan.
Melangkaui Sekadar Mengira
Imbasan yang sama boleh dikembangkan dengan mudah: jejaki jumlah panjang yang diliputi, atau cari setiap kedudukan apabila bilangan berubah, semuanya dalam satu laluan linear.
Semakan Pantas
Anda mengimbas peristiwa untuk mencari pertindihan maksimum.
Ringkasan
Tukarkan selang kepada peristiwa mula +1 dan tamat -1, sort peristiwa itu, kemudian imbas pembilang untuk mencari puncak. Putuskan seri dengan menamatkan sebelum memulakan. 🚀
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 “Sapuan Garis untuk Pertindihan Maksimum” percuma?
Ya — teks penuh “Sapuan Garis untuk Pertindihan Maksimum” 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 “Sapuan Garis untuk Pertindihan Maksimum”?
Kira selang serentak dengan peristiwa. 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 3 daripada 4.
Berapa lamakah pelajaran “Sapuan Garis untuk Pertindihan Maksimum” 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