Line Sweep untuk Tumpang Tindih Maksimum
Menghitung interval yang berlangsung bersamaan dengan event
Line Sweep untuk Tumpang Tindih Maksimum adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 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.
Pertanyaan tentang Tumpang Tindih Maksimum
Berapa banyak interval yang mencakup momen yang sama sekaligus? Jumlah puncaknya adalah tumpang tindih maksimum, titik tersibuk pada linimasa Anda. 📈
Berpikir dalam Peristiwa
Berhentilah memikirkan interval secara keseluruhan. Pecah masing-masing menjadi dua peristiwa: +1 saat dimulai dan -1 saat berakhir.
Buat Daftar Peristiwa
Untuk setiap interval, tambahkan peristiwa mulai dan peristiwa berakhir ke satu daftar bersama. Setiap peristiwa membawa posisi dan perubahan plus atau minus satu.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Urutkan Peristiwa
Urutkan setiap peristiwa berdasarkan posisi agar Anda dapat menyapu linimasa dari kiri ke kanan dan memproses perubahan dalam urutan yang tepat.
events.sort()Sapu dan Hitung
Telusuri peristiwa yang telah diurutkan sambil mempertahankan pencacah berjalan. Tambahkan setiap perubahan saat melewatinya, dan pencacah menunjukkan berapa interval yang sedang aktif.
active = 0
for pos, delta in events:
active += deltaLacak Puncaknya
Setelah setiap pembaruan, bandingkan pencacah dengan nilai terbaik sejauh ini. Nilai terbesar yang pernah dicapai pencacah adalah tumpang tindih maksimum.
best = max(best, active)Trik Pemecah Seri
Pada posisi yang sama, urutan sangat penting. Jika akhir pada x harus membebaskan slot sebelum mulai pada x, urutkan akhir sebelum mulai pada titik yang sama.
Sandi Perubahan agar Terurut dengan Benar
Cara praktis untuk memecahkan seri adalah memilih perubahan sedemikian rupa agar pengurutan tuple melakukannya untuk Anda. Letakkan perubahan -1 di depan perubahan +1 saat posisinya sama.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieMengapa Cepat
Anda membuat 2n peristiwa, mengurutkannya sekali, lalu menyapunya sekali. Seluruh metode ini adalah O(n log n), dengan biaya terbesar berasal dari satu pengurutan tersebut.
Penerapannya
Tumpang tindih maksimum menjawab soal klasik seperti jumlah minimum ruangan yang diperlukan untuk rapat, atau jumlah pengguna yang aktif secara bersamaan di sebuah server.
Bukan Sekadar Menghitung
Penyapuan yang sama dapat diperluas dengan mudah: lacak total panjang yang tercakup, atau temukan setiap posisi tempat jumlah berubah, semuanya dalam satu lintasan linear.
Pemeriksaan Cepat
Anda menyapu peristiwa untuk menemukan tumpang tindih maksimum.
Ringkasan
Ubah interval menjadi peristiwa mulai +1 dan berakhir -1, urutkan, lalu sapu pencacah untuk menemukan puncaknya. Pecahkan seri dengan mengakhiri sebelum memulai. 🚀
Belajar Python dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Line Sweep untuk Tumpang Tindih Maksimum” gratis?
Ya — teks lengkap “Line Sweep untuk Tumpang Tindih Maksimum” 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 “Line Sweep untuk Tumpang Tindih Maksimum”?
Menghitung interval yang berlangsung bersamaan dengan event 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 3 dari 4.
Berapa lama pelajaran “Line Sweep untuk Tumpang Tindih Maksimum” 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
- Mengurutkan Interval Berdasarkan Awal
- Menggabungkan Interval yang Tumpang Tindih
- Line Sweep untuk Tumpang Tindih Maksimum
- Penghapusan Minimum agar Tidak Tumpang Tindih