Pemilihan Aktivitas Berdasarkan Selesai Terawal
Menjadwalkan sebanyak mungkin acara yang tidak saling tumpang tindih
Pemilihan Aktivitas Berdasarkan Selesai Terawal 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.
Masalah Penjadwalan
Diberikan aktivitas dengan waktu mulai dan selesai, pemilihan aktivitas meminta jumlah aktivitas terbanyak yang dapat Anda hadiri tanpa ada dua aktivitas yang tumpang tindih. 📅
Tumpang Tindih Berarti Konflik
Dua aktivitas bertabrakan jika salah satunya dimulai sebelum aktivitas lainnya selesai. Anda hanya dapat memilih satu aktivitas dari setiap pasangan yang tumpang tindih.
Aturan yang Menang
Kunci greedy adalah selalu memilih aktivitas yang selesai paling awal di antara aktivitas yang masih tersedia. Selesai lebih cepat menyisakan ruang paling banyak untuk aktivitas lain.
Urutkan Berdasarkan Waktu Selesai
Mulailah dengan mengurutkan semua aktivitas berdasarkan waktu selesai. Kini, pilihan berikutnya yang terbaik cukup berupa aktivitas berikutnya dalam urutan yang masih cocok.
events.sort(key=lambda e: e[1])Lacak Waktu Selesai Terakhir
Simpan satu variabel untuk waktu selesai pilihan terakhir. Setiap aktivitas baru harus dimulai pada atau setelah nilai ini agar kompatibel.
last_end = -1Telusuri dan Pilih
Telusuri list yang telah diurutkan satu kali. Jika suatu aktivitas dimulai pada atau setelah last_end, ambil aktivitas itu dan perbarui last_end ke waktu selesainya.
for s, f in events:
if s >= last_end:
count += 1
last_end = fBerjalan dalam n log n
Biayanya adalah proses sort, O(n log n), kemudian satu lintasan linear. Ini cukup cepat bahkan untuk input kontes yang sangat besar.
Mengapa Selesai Paling Awal Menang
Selesai terlebih dahulu membebaskan jadwal secepat mungkin, sehingga tidak mungkin menghalangi rencana yang lebih baik. Menukarnya ke dalam jadwal optimal tetap menghasilkan kualitas yang sama.
Mulai Paling Awal Gagal
Memilih berdasarkan waktu mulai paling awal dapat mengambil satu aktivitas panjang yang menghabiskan sepanjang hari. Durasi saja juga dapat menyesatkan, jadi percayakan pilihan pada waktu selesai.
Tangani Sentuhan Batas
Tentukan apakah aktivitas yang selesai tepat ketika aktivitas lain dimulai dianggap bertabrakan. Gunakan s >= last_end untuk mengizinkan aktivitas yang berlangsung berturut-turut.
Bentuk Umum dalam Kontes
Pola ini tersembunyi di balik banyak tugas: memesan ruangan, menonton acara, atau menjalankan pekerjaan. Kenali polanya, maka aturan selesai paling awal dapat diterapkan.
Pemeriksaan Cepat
Anda menginginkan jumlah maksimum aktivitas yang tidak saling tumpang tindih.
Ringkasan
Urutkan aktivitas berdasarkan waktu selesai, lalu ambil setiap aktivitas yang dimulai setelah pilihan terakhir Anda selesai. Satu pengurutan ditambah satu lintasan menghasilkan himpunan maksimum. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pemilihan Aktivitas Berdasarkan Selesai Terawal” gratis?
Ya — teks lengkap “Pemilihan Aktivitas Berdasarkan Selesai Terawal” 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 “Pemilihan Aktivitas Berdasarkan Selesai Terawal”?
Menjadwalkan sebanyak mungkin acara yang tidak saling 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 “Pemilihan Aktivitas Berdasarkan Selesai Terawal” 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
- Pola Pikir Greedy
- Pemilihan Aktivitas Berdasarkan Selesai Terawal
- Knapsack Pecahan Berdasarkan Rasio
- Mengenali Saat Greedy Gagal